Bedao Mini Contest 18 - MAXKSEG

Xem dạng PDF

Gửi bài giải


Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

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ột dãy số nguyên ~A~ độ dài ~N~. Tìm ra ~K~ đoạn con liên tiếp không có phần tử chung, không rỗng sao cho tổng của tất cả phần tử được chọn là lớn nhất.

Input

  • Dòng đầu tiên gồm hai số nguyên dương ~K, N~ ~(1 \leq N \leq 10^5, 1 \leq K \leq min(N, 100))~.

  • Dòng tiếp theo gồm ~N~ số nguyên cách nhau bởi dấu cách ~A_1, A_2, \ldots, A_N~ ~(-10^9 \leq A_i \leq 10^9)~.

Output

  • In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

Sample Input 1

7 3
1 -2 3 -4 5 -6 7

Sample Output 1

15

Sample Input 2

7 3
3 -2 3 -4 7 -6 7

Sample Output 2

18

Note

  • Có ~\frac{18}{61}~ tests thoả mãn ~k = 2~.

  • Có ~\frac{18}{61}~ tests thoả mãn ~k = 3~.

  • Các tests còn lại không có ràng buộc gì thêm.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.