Furik and Rubik and Sub Array
All submissions for this problem are available.
Furik and Rubik are playing the game Sub array. This game is played over an array of integers, consisting of N elements.
In this game, Furik decides an integer that is equal to sum of some sub-array of this array and Rubik wants to guess this number.
But, since Rubik is a busy man, he wants to know how many times in the worst case he will have to try to guess this number. You may assume he acts optimally, i.e. he doesn't call the same number twice, and calls only those numbers, that might have been decided by Furik, meaning, the sum of some or the other sub-array.
Let's call the array b, sub-array of the array a, if there are numbers l and r such, that b1 = al AND b2 = al+1 AND ... b|b| = ar, where |b| is the length of the array b.
The first line contains the positive integer N. The second line contains N positive integers, which are the elements of the array.
Output a single line containing the answer to the problem.
Test Files with Time Limit set to 2 seconds
1 ≤ N * S ≤ 1010, where S is the sum of the elements in the array.
Test Files with Time Limit set to 4 seconds
1 ≤ N * S ≤ 4 * 1010
Input 3 1 2 3 Output 4 Input 9 6 1 7 3 7 1 8 5 7 Output 28
Test Case 1: Furik can decide one of the following numbers: 1, 2, 3, 5, 6. For example, let us assume Furik has decided 3. In the worst case, Rubik may call out 4 numbers, since there are only 5 such numbers.
|Tags||fft, hard, july13, maths, sereja|
|Time Limit:||2 - 4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.