Bedao OI Contest 4 - Đoạn con liên tiếp lớn nhất

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 3.0s
Memory limit: 256M
Input: maxsub.inp
Output: maxsub.out

Author:
Problem types
Allowed languages
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

Comments

Please read the guidelines before commenting.



  • -56
    Loc2008  commented on Dec. 27, 2023, 8:27 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.