TopCoder

skylinebaby
激しい「喜び」はいらない… そのかわり深い「絶望」もない……… 「植物の心」のような人生を… そんな「平穏な生活」こそ私の目標だったのに………

User's AC Ratio

82.6% (213/258)

Submission's AC Ratio

27.7% (395/1427)

Tags

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$,所有項的絕對值都不超過 $10000$。當$n=k=0$ 時代表輸入結束,請不要對它做任何處理。

Output Format

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

Sample Input 1

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 1

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

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3