[Solution] Happy Subarrays Round G 2022 Solution - Kick Start 2022

Problem

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

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

Given an array A$A$ of N$N$ integers, find the result of adding the sums of all the happy subarrays in the array A$A$.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
Each test case begins with one line consisting an integer N$N$ denoting the number of integers in the input array A$A$. Then the next line contains N$N$ integers A1,A2,…,AN${\mathbf{A}}_{\mathbf{1}},{\mathbf{A}}_{\mathbf{2}},\dots ,{\mathbf{A}}_{\mathbf{N}}$ representing the integers in given input array A$A$.

Output

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Limits

Time limit: 25 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
−800≤Ai≤800$-800\le {\mathbf{A}}_{\mathbf{i}}\le 800$, for all i$i$.

Test Set 1

1≤N≤200$1\le \mathbf{N}\le 200$.

Test Set 2

For at most 30 cases:
1≤N≤4×105$1\le \mathbf{N}\le 4\times {10}^5$.
For the remaining cases:
1≤N≤200$1\le \mathbf{N}\le 200$.