MUSIC - Musical Optimization

no tags 

Bessie the cow used to write musical melody. A musical melody is represented as a sequence of N (1 <= N <= 100,000) notes numbered 1..N. Note i is represented by the integer Ai (-10,000 <= Ai <= 10,000).

To Bessie's cow-like mind, a musical melody is called 'perfect' if and only if the sum of all the notes in any of its consecutive subsequences is strictly positive.

For a given musical melody, Bessie wants to make it perfect, but she wants to change the melody as little as possible.

Thus, to perfect the melody, she repeatedly chooses a consecutive subsequence of the melody, [x, y] (1 < x <= y < N), whose sum S is negative. Then she adds S to both Ax-1 and Ay+1, while subtracting S from both Ax and Ay. (It is possible to subtract from the same note twice if x = y.)

Given a musical melody, compute the minimum number of steps to make the melody perfect.


* Line 1: The single integer N.

* Lines 2..N+1: Line i+1 contains the single integer Ai.


* Line 1: A single integer that represents the minimum number of steps needed to make the given musical melody perfect. If there are no solutions, output -1 instead.




There is a musical melody with length of 5. The notes are (13, -3, -4, -5, 62).

First, we choose the range [2, 4]; its sum is (-3) + (-4) + (-5) = -12. After the first step, the melody becomes (1, 9, -4, 7, 50). Second, we choose the range [3, 3], whose sum is -4, and the melody after the second step becomes (1, 5, 4, 3, 50). The melody is perfect now.

Warning: large input/output data, be careful with certain languages

Added by:Fudan University Problem Setters
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Lei HUANG [g201513] , used in USACO