Non-decreasing towers

Revision en3, by IMAN_GH, 2016-05-23 21:39:10

Consider array A with n elements.
In one operation you can decrease A[i] and increase A[i+1] (i < n & A[i] > 0).
g(A) equals the minimum number of operations to make array A non-decreasing.

Subtasks :

-- n <= 800 , 0 <= A[i] <= 10^3 , g(A) is required.
-- n <= 10^4 , 0 <= A[i] <= 10^12 , g(A) is required.

-- n <= 800 , 0 <= A[i] <= 10^12 , The sum of g for all A substrings is required.
-- n <= 10^4 , 0 <= A[i] <= 10^12 , The sum of g for all A substrings is required.

All of them mod 10^9 + 7.

(This problem prepared for CodeShark#4)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English IMAN_GH 2016-05-23 21:39:10 1 Tiny change: 'is problems prepared ' -> 'is problem prepared '
en2 English IMAN_GH 2016-05-23 20:56:15 28 (published)
en1 English IMAN_GH 2016-05-23 20:53:34 605 Initial revision (saved to drafts)