TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

87.8% (36/41)

Submission's AC Ratio

25.5% (62/243)

Description


給你一個數列S,一個該數列的連續和(Continuous Sum,以下簡稱CS)是指S當中的某些連續項之總和。

很容易算得出來,一個總長度為項的數列S,其連續和(CS)共有 $\displaystyle \frac{n(n+1)}{2}$ 個。 注意,問題來囉!

請問,這 $\displaystyle \frac{n(n+1)}{2}$ 個連續和(CS)之中,第k大的是多少?

Input Format

輸入檔可能包含多筆測試資料。每筆測試資料佔兩列,第一列有兩個正整數$n,k$ ($1\leq n\leq 20000, 1\leq k\leq \displaystyle \frac{n(n+1)}{2}$)。第二列總共有n個以空白隔開的整數,代表數列S,所有項的絕對值都不超過10,000。當n=k=0時代表輸入結束,請不要對它做任何處理。

Output Format

對於輸入的每一筆測試資料,請輸出第k大的連續和。

Sample Input

5 1
1 2 3 4 5
5 10
1 2 3 4 5
5 15
1 2 3 4 5
7 3
1 1 1 1 1 1 1
0 0

Sample Output

15
5
1
6

Hints

前三筆測試資料中,所有的連續和列在下表:

  1  2  3  4  5
   3  5   7  9
    6   9  12
     10  14
       15

於是可得最大之連續和為15,第15大之連續和為1。

※本題徵求比參考答案更好的解答XD!

※2008/02/25題目敘述修正:感謝Tommy!
※2008/02/26輸入敘述修正:感謝csftwpt!

Problem Source

原TIOJ1208 / TIOJ 2008例行賽02-Elite (prob J)。Idea:kelvin。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536