Page not loading? Try clicking here.
Placeholder

#8424
Subtask

행복한 수열 10s 1024MB

Problems

Let us define F(B, L, R) as the sum of a subarray of an array B bounded by indices L and R (both inclusive). Formally, F(B, L, R) = B_L + B_{L+1} + \cdots + B_R.

An array C of length K is called a happy array if all the prefix sums of C are non-negative. Formally, the terms F(C, 1, 1), F(C, 1, 2), \dots, F(C, 1, K) are all non-negative.

Given an array \mathbf{A} of \mathbf{N} integers, find the result of adding the sums of all the happy subarrays in the array \mathbf{A}.


Input

The first line of the input gives the number of test cases, \mathbf{T}. \mathbf{T} test cases follow. (1 \le T \le 100)

Each test case begins with one line consisting an integer \mathbf{N} denoting the number of integers in the input array \mathbf{A}. Then the next line contains \mathbf{N} integers \mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N} representing the integers in given input array \mathbf{A}. (-800 \le \mathbf{A_i} \le 800)


Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the result of adding the sums of all happy subarrays in the given input array \mathbf{A}.


Subtask

# Score Condition
#130

1\le N\le 200

#270

For at most 30 cases: 1 \le \mathbf{N} \le 4 \times 10^5.

For the remaining cases: 1 \le \mathbf{N} \le 200.


Example 

2
5
1 -2 3 -2 4
3
1 0 3
Case #1: 14
Case #2: 12

In Sample Case #1, the happy subarrays are [1], [3], [3, -2], [3, -2, 4], and [4] with their respective sums 1, 3, 1, 5, and 4. After adding the sums obtained, the result is 14.

In Sample Case #2, the happy subarrays are [1], [1, 0], [1, 0, 3], [0], [0, 3], and [3] with their respective sums 1, 1, 4, 0, 3, and 3. After adding the sums obtained, the result is 12.



Source

Google Kick Start 2022 Round G C번
You must sign in to write code.