KSS - MarisaOJ: Marisa Online Judge

KSS

Time limit: 1000 ms
Memory limit: 256 MB
Given an array $a$ consisting of $n$ integer elements and a positive integer $k$, print the value of the $k$-th largest sum of any contiguous subarray. (There are $\frac{n \times (n + 1)}{2}$ contiguous subarrays in the array). ### Input - The first line contains two positive integers $n$ and $k$. - The second line contains $n$ integers describing the array $a$. ### Output - Print the value of the $k$-th largest sum of any contiguous subarray. ### Constraints - $1 \le n \le 10^5$. - $1 \le k \le \frac{n \times (n + 1)}{2}$. - $|a_i| \le 10^9$. ### Example Input: ``` 4 3 1 -1 2 -2 ``` Output:: ``` 1 ``` Explanation: Subarrays $[1, 3]$ and $[3, 3]$ have the largest sums of $2$. The next largest sums are from subarrays $[1, 1]$ and $[2, 3]$, each with a sum of $1$. Therefore, the $k$-th largest sum is $1$.