Problem G
Flow Shop
$N$ swathers have been ordered and there are $M$ stages in the manufacturing process. The swathers will each go through the same sequence of stages.
In particular, the processing occurs as follows: For each swather $i$ and each stage $j$, it takes $P_{i,j}$ units of time to complete stage $j$ for swather $i$. The workers at each stage may only work on one swather at a time. At the start of the day all swather orders are ready to be processed by the first stage. At any point in the process, if the workers at stage $j$ are idle and there are swathers waiting to be processed at this stage then the workers will pick the swather that has the lowest label (they are labelled from $1$ to $N$). Note that the work on a stage $j$ can only be started after the work on the stage $j-1$ is completed.
Determine the time each swather is completed.
Input
There is only one test case in each file. It begins with a single line containing $N$ and $M$ ($1 \leq N,M \leq 1000$), the number of swathers and stages (respectively). Following this are $N$ lines, each with $M$ integers. The $j$’th integer of the $i$’th line is $P_{i,j}$, giving the amount of time it will take for the workers at stage $j$ to complete swather $i$ ($1 \leq P_{i,j} \leq 10^6$).
Output
Output a single line containing $N$ integers $T_1~ T_2~ \ldots ~ T_ n$ with a single space between consecutive integers. These should be such that stage $M$ for swather $i$ is completed at time $T_ i$.
Sample Input 1 | Sample Output 1 |
---|---|
2 3 1 2 3 3 2 1 |
6 7 |
Sample Input 2 | Sample Output 2 |
---|---|
3 2 3 1 4 7 2 5 |
4 14 19 |