Atcoder Educational DP Contest W - Intervals
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Xét một xâu có chiều dài ~N~ bao gồm các chữ số 0 và 1. Điểm của xâu được tính như sau:
- Với mỗi số nguyên ~i~ (~1~ ≤ ~i~ ≤ ~M~), tổng số điểm của xâu được tăng thêm ~a_i~ nếu như xâu con bao gồm các kí tự từ ~l_i~ đến ~r_i~ (kể cả biên) có ít nhất một kí tự
1.
Với mọi xâu độ dài ~N~, số điểm cao nhất có thể đạt được là bao nhiêu?
Input
- Dòng đầu chứa hai số nguyên ~N, M~ (~1 \le N \le 2 \cdot 10^5~ và ~1 \le M \le 2 \cdot 10^5~).
- ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~l_i, r_i, a_i~ (~1 \le l_i \le r_i \le N~ và ~\mid a_i\mid \le 10^9~).
Output
Số điểm tối đa mà xâu có thể đạt được.
Sample 1
Input
5 3
1 3 10
2 4 -10
3 5 10
Output
20
Giải thích
Điểm cho xâu 10001 là ~a_1 + a_3 = 10 + 10 = 20~.
Sample 2
Input
3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30
Output
90
Giải thích
Điểm cho xâu 100 là ~a_1 + a_2 = 100 + (-10) = 90~.
Sample 3
Input
1 1
1 1 -10
Output
0
Giải thích
Điểm cho xâu 0 là ~0~.
Sample 4
Input
1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
Output
5000000000
Kết quả có thể không phù hợp với số nguyên có định dạng 32-bit.
Sample 5
Input
6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7
Output
10
Giải thích
Điểm cho xâu 101000 là ~a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10~.
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.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.