L - K-th Abs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
A の連続した空でない部分列 B に対して B のスコアを (B に含まれる要素の総和の絶対値 ) と定めます。
A の連続した空でない部分列は全部で \frac{N(N+1)}{2} 個ありますが、それらの部分列全てに対してスコアを計算したとき、小さい方から K 番目のスコアを求めてください。

制約

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq K \leq \frac{N(N+1)}{2}
  • -10^9 \leq A_i \leq 10^9
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \dots A_N

出力

小さい方から K 番目のスコアを出力せよ。

入力例 1

2 2
2 -3

出力例 1

2

A の連続した空でない部分列およびスコアは次の通りです。

  • 列 (A_1) のスコアは | 2 | = 2 です。
  • 列 (A_2) のスコアは | -3 | = 3 です。
  • 列 (A_1, A_2) のスコアは | 2 + (-3) | = 1 です。

入力例 2

5 10
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 2

3000000000

答えが 32 bit 整数に収まらない可能性があることに注意してください。

入力例 3

7 22
3 -1 4 -1 5 -9 2

出力例 3

5

Score : 6 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are given a sequence of length N: A = (A_1, A_2, \dots, A_N).
For a non-empty contiguous subsequence B of A, let the score of B be the absolute value of the sum of elements in B.
Assume that we have computed the scores of all \frac{N(N+1)}{2} non-empty contiguous subsequences of A. Find the K-th smallest of these scores.

Constraints

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq K \leq \frac{N(N+1)}{2}
  • -10^9 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the K-th smallest of these scores.

Sample Input 1

2 2
2 -3

Sample Output 1

2

The non-empty contiguous subsequences of A and their scores are as follows.

  • The sequence (A_1) has a score of | 2 | = 2.
  • The sequence (A_2) has a score of | -3 | = 3.
  • The sequence (A_1, A_2) has a score of | 2 + (-3) | = 1.

Sample Input 2

5 10
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

3000000000

Note that the answer may not fit into a 32-bit integer.

Sample Input 3

7 22
3 -1 4 -1 5 -9 2

Sample Output 3

5