KSS - MarisaOJ: Marisa Online Judge

Given an array

a

$a$ consisting of

n

$n$ integer elements and a positive integer

k

$k$ , print the value of the

k

$k$ -th largest sum of any contiguous subarray. (There are

\frac{n \times (n + 1)}{2}

$\frac{n \times (n + 1)}{2}$ contiguous subarrays in the array). ### Input - The first line contains two positive integers

n

$n$ and

k

$k$ . - The second line contains

n

$n$ integers describing the array

a

$a$ . ### Output - Print the value of the

k

$k$ -th largest sum of any contiguous subarray. ### Constraints -

1 \leq n \leq 10^{5}

$1 \le n \le 10^5$ . -

1 \leq k \leq \frac{n \times (n + 1)}{2}

$1 \le k \le \frac{n \times (n + 1)}{2}$ . -

| a_{i} | \leq 10^{9}

$|a_i| \le 10^9$ . ### Example Input:

431 - 12 - 2

$4 3 1 -1 2 -2$

Output::

1

$1$

Explanation: Subarrays

[1, 3]

$[1, 3]$ and

[3, 3]

$[3, 3]$ have the largest sums of

2

$2$ . The next largest sums are from subarrays

[1, 1]

$[1, 1]$ and

[2, 3]

$[2, 3]$ , each with a sum of

1

$1$ . Therefore, the

k

$k$ -th largest sum is

1

$1$ .

Topic

Binary search

Data structure

Rating

1500

Solution (0)

Solution