I am a beginner , I know what is prefix sums method and its implementation using partial_sum() STL and without it too. But , I can’t understand how it can be used to solve this problem. If anyone has solved this using prefix-sums in c++ , please help me in understanding it how can it be done. It will be a great help.
Here’s the link to the problem.
THANKS IN ADVANCE…
Thanks :).
Can you explain your approach a little bit too please ?
Initially i found out number of empty spaces in each of the rows. I calculated in O(n) in the following way:-
Say the answer for the ith row be x. So the answer for the (i+1)th row would be:
x - no. of empty blocks which end at the ith row + no. of empty blocks which start at the (i+1)th row.
now store the total of the first h blocks in a variable. Then you can find the answer for all the blocks of height h. Find the maximum among them and subtract it from (n*h) and you are done!!!
Hope it helps!!!
For each i in the way, you need to calculate number of empty spaces. The optimal solution is that range of size of the truck where this number is maximum. So, you need to do two tasks:
For 1 you can use BIT/Segment tree but since the value to be added is known beforehand (1 in this case), there is a faster method. You can take an array ‘a’ initilised to 0 and incrementing a[l] and decrement a[r+1] for every range. After doing the prefix sum of this array you’re left with updated indices.
for 2nd part you can further take the prefix sum of previously generated array and check the maximum sum of range of size k.
You may have a look on my solution for this same approach here :
https://www.codechef.com/viewsolution/7721510
Hope it helps 
number of spaces in current row = spaces in prev row + empty spaces starting from current row - empty spaces ending at current row.
solution same as anuppam’s(above) approach.