QTGIFT1 - New year love story

Sau một năm dài cố gắng, cuối cùng ĐB cũng đã cưa đổ TN. Nhưng TN là một cô gái nhìn xa thông rộng, nên đã tiên liệu trước được chuyện hai người chia tay và ĐB sẽ đòi quà. Tuy ĐB đã khẳng định không đòi lại quà, nhưng TN cứ khăng khăng nói phải tính chuyện này cho rõ ràng. ĐB nói TN cứ tự quyết định việc đó, nên TN đã đưa ra điều kiện như sau:

Giả sử ĐB tặng TN n món quà, mỗi món có giá trị a[i] (i = 1..n). TN sẽ lấy máy tính chọn một số k ngẫu nhiên (1 ≤ k ≤ n). Vậy trong n món quà, ĐB không được đòi lại k món liên tiếp.

Hãy giúp TN tính xem ĐB có thể đòi lại quà với tổng giá trị lớn nhất là bao nhiêu

Input : 

Dòng 1 : gồm 2 số n và k

Dòng 2 : gồm n số, số thứ i là a[i] (i = 1..n), các số cách nhau ít nhất một khoảng trắng

Output : 

Một số duy nhất là tổng giá trị quà lớn nhất mà ĐB có thể đòi được 

Giới hạn : 

 - 0 ≤ a[i] ≤ 106

 - n ≤ 106

Ví dụ : 

Input:

5 3

6 19 8 7 13

Output:

45

 

Bonus :

 


Added by:Coder nhà mình
Date:2014-01-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Tài liệu chuyên tin

hide comments
2018-12-14 16:41:25
Test cases are extremely weak, my worst case O(n^3) solution gave AC
2017-11-27 16:48:02
This problem is required to be solved with algorithm costing O(N) time complexity. My first O(N log2(N)) solution got TLE.
2017-02-19 12:11:53 Dimitris Rontogiannis
O(n log N) gets TLE, but with fast I/O it gets AC!
2015-03-02 08:51:39 Amit Ajaat
Please explain question correctly. If he can't take 3 packs in a row, in the given testcase then maximum sum is 53 corresponding to all i.e. He may have taken all 5 packs in a row. Isn't it.
2015-01-23 06:53:43 ­
Vietnamese's story is far different from English's =))
2015-01-23 06:53:43 aristofanis
O(n log n) gets TLE... Is there anything faster, or just constant optimisation is required?
EDIT: Never mind, I got AC with a O(n) algo.. Really nice problem!

Last edit: 2014-04-22 16:31:59
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.