1208 . 第K大連續和

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

82.6% (213/258)

Submission's AC Ratio

27.7% (395/1427)

Tags

TIOJcon 2008-TIOJcon-2nd CKsim 2015-CKsim-3rd

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

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

　　１　　２　　３　　４　　５
　　　３　　５　　　７　　９
　　　　６　　　９　　１２
　　　　　１０　　１４
　　　　　　　１５

於是可得最大之連續和為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
Submit out of contest
Back to Top