Chọn không quá K đoạn con liên tiếp, đôi một không giao nhau, để tổng các phần tử được chọn lớn nhất. Mỗi đoạn phải chứa ít nhất một phần tử; bạn cũng được phép không chọn đoạn nào.
Input
Dòng đầu chứa hai số nguyên N và K.
Dòng thứ hai chứa N số nguyên Ai.
Output
In tổng độ hài lòng lớn nhất có thể đạt được.
Constraints
1≤K≤N≤3⋅105.
∣Ai∣≤109.
Scoring
Subtask 1 (50% số điểm): dữ liệu nằm trong miền nhỏ, phù hợp với lời giải vét cạn hoặc DP trực tiếp được mô tả trong tài liệu.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
7 2
4 -6 5 3 -10 7 2
Output
17
Giải thích: Chọn hai đoạn gồm các giá trị 5,3 và 7,2, thu được tổng 8+9=17. Mọi cách dùng không quá hai đoạn đều không cho tổng lớn hơn.
Lời giải tóm tắt
Mô hình: Chọn không quá K đoạn con liên tiếp, đôi một không giao nhau, để tổng các phần tử được chọn lớn nhất; có thể không chọn đoạn nào. Đại lượng bị giới hạn về số lượng được chuyển thành một khoản phạt hoặc phần thưởng, nhờ đó bỏ được chiều đếm lớn khỏi DP hay thuật toán tối ưu cơ sở.
Thuật toán: Gắn một mức phạt cho mỗi lần mở đoạn, rồi dùng DP hai trạng thái ngoài đoạn và trong đoạn; nhị phân mức phạt để khôi phục giá trị tại nhiều nhất K đoạn.
Chứng minh đúng: Với một mức phạt cố định, DP xét mọi cách kết thúc trước vị trí hiện tại: trạng thái ngoài đoạn giữ phương án tốt nhất đã đóng, còn trạng thái trong đoạn hoặc kéo dài đoạn cũ hoặc mở đoạn mới. Vì mỗi nghiệm bị trừ đúng mức phạt nhân số đoạn, DP trả đúng cực đại biến đổi. Khi mức phạt tăng, nghiệm tối ưu không thể dùng nhiều đoạn hơn; phá hòa theo số đoạn lớn bảo đảm tính đơn điệu. Tại ngưỡng cuối còn dùng ít nhất K đoạn, cộng lại lambda*K khôi phục giá trị của đường bao lõm; riêng nếu lambda=0 đã dùng không quá K đoạn thì đó chính là nghiệm của bài “không quá K”.
Độ phức tạp: Mỗi lần đánh giá O(N), tổng O(N log V) thời gian và O(1) bộ nhớ ngoài mảng input.