Problem 3: Milk Scheduling [Kalki Seksaria, 2013]

Farmer John's N cows (1 <= N <= 10,000) are conveniently numbered 1..N. Each cow i takes T(i) units of time to milk. Unfortunately, some cows must be milked before others, owing to the layout of FJ's barn. If cow A must be milked before cow B, then FJ needs to completely finish milking A before he can start milking B.

In order to milk his cows as quickly as possible, FJ has hired a large number of farmhands to help with the task -- enough to milk any number of cows at the same time. However, even though cows can be milked at the same time, there is a limit to how quickly the entire process can proceed due to the constraints requiring certain cows to be milked before others. Please help FJ compute the minimum total time the milking process must take.

#3822 upload 3 done 2 how_to_reg 2

Milk Scheduling timer 1s memory 128MB

#3822

Milk Scheduling 1s 128MB