ĐỀ KIỂM TRA ĐỘI TUYỂN HSG LẦN 3 - Ôn Hải Phòng T11/2020
Gug đang chuẩn bị một bữa tiệc cho bạn bè của mình. Bữa tiệc bao gồm đĩa thức ăn được sắp xếp thành một hàng duy nhất, với đĩa thứ từ bên trái mang lại cho điểm hài lòng nếu ăn. Vì một số đĩa thức ăn có thể bị thối, có thể âm tính.
Có tổng cộng người tham gia vào bữa tiệc, và mỗi người sẽ được chỉ định một phân khúc đĩa liên tiếp để tiêu thụ. Phân khúc này có thể có thể trống. Phân khúc của hai người không thể trùng nhau, vì thức ăn không thể ăn hai lần. Gug muốn gán các đĩa cho bạn bè của mình sao cho tổng điểm hài lòng của tất cả các đĩa thức ăn được tiêu thụ là tối đa.
Dữ liệu vào:
Dòng đầu có hai số nguyên và ;
Dòng tiếp theo sẽ chứa số nguyên .
Dữ liệu ra:
Ghi ra một số nguyên duy nhất trên một dòng, tổng điểm hài lòng trong một bài tập tối ưu.
Ví dụ:
Dữ liệu vào:
6 1
1 -2 3 -1 5 -6
Dữ liệu ra:
7
Dữ liệu vào:
6 2
1 2 3 -10 5 6
Dữ liệu ra:
17
Dữ liệu vào:
6 4
-1 -2 -1 0 -5 -1
Dữ liệu ra:
0
Giới hạn:
Subtask số điểm có ;
Subtask số điểm khác thỏa trong dãy có nhiều nhất một giá trị ;
Subtask số điểm khác có ;
Subtask số điểm khác có ;
Subtask số điểm khác có ;
Subtask số điểm khác có ;
Subtask số điểm cuối cùng không có ràng buộc gì thêm.
