KSUM - Món quà của thầy Kiên
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Trong lớp học của thầy Kiên, Bờm là một học sinh vô cùng xuất sắc. Hôm nay, Bờm lại tiếp tục đứng nhất trong một Contest giữa các trường, vì thế thầy Kiên quyết định sẽ tặng Bờm một ít kẹo xem như phần thưởng.
Thầy Kiên có ~n~ viên kẹo được đánh số lần lượt từ ~1~ đến ~n~. Viên kẹo thứ ~i~ có độ ngon ~w_i~. Hôm nay, thầy quyết định tặng Bờm ~k~ viên kẹo liên tiếp ~(1 ≤ k ≤ n)~ trong ~n~ viên kẹo. Mặc khác, vì Bờm rất xuất sắc nên thầy Kiên muốn tổng độ ngon của những viên kẹo Bờm nhận được là lớnnhất. Bạn hãy giúp thầy Kiên tính toán tổng độ ngon của những viên kẹo mà Bờm sẽ nhận được nhé!
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ và ~k~ ~(k ≤ n ≤ 10^5)~ là số lượng kẹo của thầy Kiên;
- Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa duy nhất một số nguyên ~w_i~ là độ ngon của viên kẹo thứ ~i~ ~(1 ≤ w_i ≤ 10^9)~.
Giới hạn:
- ~40\%~ số test có ~k ≤ n ≤ 10000~;
- ~60\%~ số test còn lại không có giới hạn gì thêm.
Output
- Đưa ra kết quả bài toán trên một dòng.
Sample
Input #1
5 2
4
3
2
6
1
Output #1
8
Hint
- Thầy Kiên cần chọn ~2~ viên kẹo liên tiếp sao cho tổng độ ngon là lớn nhất, vì thế thầy sẽ chọn viên kẹo thứ ~3~ và viên kẹo thứ ~4~.
Problem source: Kc97ble - Free Contest
Bình luận
LƯU Ý :Là không được thay đổi mảng đâu nhé , bài bắt mình tính tổng các phần trong đoạn con có K phần tử nhé .Thì mình làm theo tư tưởng preFixSum thôi . Trước hết là lưu giá trị của S[i] từ i=1 đến n , S[i]=S[i-1]+a[i-1 ],sét S[0]=0 nhé (công thức tính tổng các phần tử trong mảng của đoạn từ [0,i]) =>ta sẽ được mảng S{0,4,7,9,15,16} ... sau đó mình so sánh khoảng cách giữa các S[i]-S[i-k] với i chạy từ k đến n Fan MU Mãi ĐỈnh///