Bedao OI Contest 4 - Đoạn con liên tiếp lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
3.0s
Giới hạn bộ nhớ:
256M
Input:
maxsub.inp
Output:
maxsub.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho mảng ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ và một số nguyên ~k~. Tìm đoạn ~[l,r]~ thỏa mãn ~(r-l+1) \ge k~, và tổng các số trong đoạn ~[l,r]~ trừ đi tổng của ~k~ số lớn nhất trong đoạn ~[l,r]~ đạt giá trị lớn nhất.
Nói cách khác, đặt ~S[l,r]~ = tổng các số trong đoạn ~[l,r]~, ~T[l,r]~ = tổng ~k~ số lớn nhất trong đoạn ~[l,r]~, hãy tìm ~[l,r]~ thỏa mãn ~S[l,r] - T[l,r]~ đạt giá trị lớn nhất.
Yêu cầu: In ra giá trị lớn nhất tìm được.
Input
Vào từ file văn bản maxsub.inp:
Dòng đầu gồm hai số nguyên ~n, k~ (~1 \le n \le 3 \cdot 10^5, 0 \le k \le min(n, 100)~).
Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~).
Output
Đưa ra file văn bản maxsub.out một số nguyên duy nhất là kết quả cần tìm.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10~ | ~n \le 200~ |
| 2 | ~10~ | ~n \le 2000~ |
| 3 | ~10~ | ~k = 0~ |
| 4 | ~20~ | ~k = 1~ |
| 5 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
10 2
-5 9 -1 -1 6 8 -10 10 -2 5
Sample Output 1
5
Sample Input 2
4 2
-6 -8 4 10
Sample Output 2
0
Sample Input 3
2 1
2 6
Sample Output 3
2
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.