## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

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

### Problem

Let us define $F\left(B,L,R\right)$ as the sum of a subarray of an array $B$ bounded by indices $L$ and $R$ (both inclusive). Formally, $F\left(B,L,R\right)={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\left(C,1,1\right),F\left(C,1,2\right),\dots ,F\left(C,1,K\right)$ are all non-negative.

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

### Input

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

### Output

For each test case, output one line containing Case #x$x$: y$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 $A$.

Solution Click Below:-  👉
👇👇👇👇👇

### Limits

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

#### Test Set 1

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

#### Test Set 2

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