26434번 - Happy Subarrays 서브태스크다국어

문제

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}$.

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

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}$.

출력

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}$.

제한

• 1ドル \le \mathbf{T} \le 100$.
• $-800 \le \mathbf{A_i} \le 800,ドル for all $i$.

Test Set 1 (11점)

• 1ドル \le \mathbf{N} \le 200$.

Test Set 2 (20점)

• For at most 30 cases:
  • 1ドル \le \mathbf{N} \le 4 \times 10^5$.
• For the remaining cases:
  • 1ドル \le \mathbf{N} \le 200$.

힌트