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