Cắt dãy
Xem dạng PDF
Gửi bài giải
Điểm:
0,79 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho số nguyên ~N~ và một dãy số nguyên ~a_{1}, a_{2}, ..., a_{N}~. Nhiệm vụ của bạn là phải cắt dãy số trên thành một số dãy số (giữ nguyên thứ tự) thỏa mãn:
- Tổng của mỗi dãy số không lớn hơn số nguyên ~M~.
- Tổng của các số lớn nhất trong các dãy trên là nhỏ nhất.
Input
- Dòng đầu gồm ~2~ số nguyên ~N~ và ~M~.
- Dòng thứ hai gồm ~N~ số nguyên của dãy ~a_{1},a_{2}, ..., a_{N}~.
Output
Gồm một số duy nhất là tổng của các số lớn nhất trong các dãy số trên. Nếu không có cách cắt nào thỏa mãn hai điều kiện trên, in ra ~-1~.
Giới hạn
Giới hạn:
- ~1 \le N \le 100000~.
- ~0 \le a_{i} \le 10^{6}~.
- ~M < 2^{63}~.
Sample Input
8 17
2 2 2 8 1 8 2 1
Sample Output
12
Note
Giải thích: Cắt thành ~3~ dãy ~2 2 2, 8 1 8, 2 1~
Bình luận
tét ye'u qua' 2 for ac ma ru`i :<>
Xam
test yếu quá mình làm 2 for cũng AC
=))))))
admin có thể add thêm 1 test dãy giảm dần 1e5 phần tử và m=s^63 -1 được ko
nờ ô nô
test yếu quá :<
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.