题目详情题解（0）讨论（0）提交记录（0）

AT_dp_w.Intervals

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

考虑一个长度为 NN、仅由 0 和 1 组成的字符串。该字符串的分数按照如下方式计算：

  • 对于每个 ii（1≤i≤M1 \leq i \leq M），如果从第 lil_i 个字符到第 rir_i 个字符之间至少包含一个 1，则将 aia_i 加到分数上。

请你求出字符串分数的最大值。

输入格式

输入以如下格式从标准输入读入。

NN MM l1l_1 r1r_1 a1a_1 l2l_2 r2r_2 a2a_2 …\ldots lMl_M rMr_M aMa_M

输出格式

输出字符串分数的最大值。

输入输出样例

  • 输入#1

    5 3
1 3 10
2 4 -10
3 5 10

    输出#1

    20

  • 输入#2

    3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

    输出#2

    90

  • 输入#3

    1 1
1 1 -10

    输出#3

    0

  • 输入#4

    1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

    输出#4

    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

    输出#5

    10

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤li≤ri≤N1 \leq l_i \leq r_i \leq N
  • ∣ai∣≤109|a_i| \leq 10^9

样例解释 1

10001 的分数为 a1+a3=10+10=20a_1 + a_3 = 10 + 10 = 20。

样例解释 2

100 的分数为 a1+a2=100+(−10)=90a_1 + a_2 = 100 + (-10) = 90。

样例解释 3

0 的分数为 00。

样例解释 4

答案可能超出 32 位整数范围。

样例解释 5

例如，101000 的分数为 a2+a3+a4+a5+a7=10+(−8)+5+9+(−6)=10a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页