Problem hidden on 2014-10-16 12:55:56 by VOJ Team

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 :

 


Được gửi lên bởi:Coder nhà mình
Ngày:2014-01-20
Thời gian chạy:0.050s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Tài liệu chuyên tin

hide comments
2019-01-27 15:13:51
time chặt quá, cin cout + ios cũng không qua nhé các bạn :((
2018-06-21 22:46:35
không có g.han gì cả
2018-06-10 10:06:49
dizzz anh khoong doi qua :D
2017-11-27 16:49:31
O(N log2(N)) vẫn bị TLE. Bài này bắt O(N) mới qua.
Deque tìm min/max AC.
2017-08-03 20:14:32
so eazy
2016-04-17 09:42:46
n log n ko acc????
2015-10-26 03:12:48 _sanghk11_
có lẽ o ( n log n ) ko ac :v

Last edit: 2015-10-27 15:53:03
2015-10-01 06:00:01 Lê Nguyên Khôi
ai giải thích cái test vd giùm !
2015-02-28 13:10:38 Trần Quang Linh
TN sẽ lấy máy tính chọn một số k ngẫu nhiên (1 ≤ k ≤ n)

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

k nguoi ta nhp vao la sao nhi
2014-12-27 21:55:57 Sơn Tùng M-TP
vào lỡ cái bài này toàn nghe nhạc k có hứng làm bài nữa. :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.