Nội dung Bài tập
- Mã:
- DHLTNC_CT3_N6_QHD_BAI_1
- Tên:
- Ăn trộm
- Dạng thi:
- oi
- Thang điểm:
- 5 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4801103024
ĂN TRỘM
Có một dãy n ngôi nhà, nhà thứ i có số tiền là ai. Có một người muốn lấy trộm tiền nhiều nhất từ các ngôi nhà trên. Mỗi lần vào được ngôi nhà, thì tên trộm sẽ lấy hết số tiền trong nhà đó. Tuy nhiên nếu tên trộm có lấy tiền trong k ngôi nhà gần đó, thì sẽ bị bắt. Hãy tìm cách cho tên trộm lấy nhiều tiền nhất có thể mà không bị bắt.
Dữ liệu vào:
-
Dòng đầu tiên gồm một số nguyên là số n và k cách nhau một khoảng trắng(1 ≤ n ≤
106).
- Dòng thứ hai ghi n số nguyên a1, a2, a3,…, an. Mỗi số cách nhau một khoảng trắng (1 ≤ ai ≤ 109).
Dữ liệu ra:
- Một số duy nhất là số tiền lớn nhất mà tên trộm lấy được mà không bị bắt.
Ví dụ:
Input
Output
6 2
1 3 5 1 5 9
15
Input
Output
6 3
1 3 5 1 5 9
14
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
#include <iostream>#include <algorithm>using namespace std;struct PS{ &n...