AT_past202109_l K番目の絶対値

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

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

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

### 注意 この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ - 入力は全て整数である。 ### Sample Explanation 1 $ A $ の連続した空でない部分列およびスコアは次の通りです。 - 列 $ (A_1) $ のスコアは $ |\ 2\ |\ =\ 2 $ です。 - 列 $ (A_2) $ のスコアは $ |\ -3\ |\ =\ 3 $ です。 - 列 $ (A_1,\ A_2) $ のスコアは $ |\ 2\ +\ (-3)\ |\ =\ 1 $ です。 ### Sample Explanation 2 答えが $ 32 $ bit 整数に収まらない可能性があることに注意してください。