시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
25 초 (추가 시간 없음) | 1024 MB | 17 | 14 | 14 | 82.353% |
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}$.
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$.
Contest > Google > Kick Start > Google Kick Start 2022 > Round G C번