#AT23. Intervals
Intervals
[W] Intervals(dp_w)
来源: AtCoder Educational DP Contest - Problem W 原题时限:2 秒 / 内存:1024 MB
题目描述
考虑一个长度为 的、仅由 0 与 1 构成的字符串。字符串的分数按下式计算:
- 对于每个 (),若字符串在第 个到第 个字符(含两端)之间至少出现一次
1,则分数加上 。
求字符串可能得到的最大分数。
输入格式
输入由标准输入按以下格式给出:
N M
l_1 r_1 a_1
l_2 r_2 a_2
:
l_M r_M a_M
输出格式
输出字符串可能得到的最大分数。
数据范围
- 输入中的所有值均为整数。
样例 1
输入:
5 3
1 3 10
2 4 -10
3 5 10
输出:
20
样例 2
输入:
3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30
输出:
90
样例 3
输入:
1 1
1 1 -10
输出:
0
样例 4
输入:
1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
输出:
5000000000
样例 5
输入:
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
输出:
10