分数: 6 点
警告
2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
你发现 N 宝箱已编号 1 通过 N。 最初,所有箱子都被锁住,无法打开。 如果您成功解锁宝箱 i,你得到 a_i 日元(日本的货币)。
在你的朋友中,有 M 锁匠,编号 1 通过 M。 如果你问锁匠 i 通过付费解锁宝箱 c_i 日元,锁匠将解锁所有仍锁在箱子中的箱子 l_i, l_i + 1, \ldots, r_i.
您的目标是最大化 Y-X,其中 X 是您支付给锁匠的总金额,并且 Y 是您从宝箱中获得的总金额。找出最大可能值 Y-X.
约束
- 输入中的所有值都是整数。
- 1 \leq N,M \leq 2 \times 10^5
- 1 \leq a_i,c_i \leq 10^9
- 1 \leq l_i \leq r_i \leq N
输入
输入由标准输入按以下格式给出:
N M a_1 a_2 \cdots a_N l_1 r_1 c_i \vdots l_M r_M c_M
输出
打印最大可能值 Y-X,其中 X 是您支付给锁匠的总金额,并且 Y 是您从宝箱中获得的总金额。
示例输入 1
4 3 20 10 100 10 1 3 100 2 4 50 1 1 50
示例输出 1
70
- 最好支付 50 日元 到 锁匠 2 并得到 10+100+10=120 解锁宝箱获得的日元 2,3,4.
- 请注意,您不必解锁所有箱子。
示例输入 2
2 2 10 10 1 1 1000 1 2 100
示例输出 2
0
- 请注意,最佳策略可能不是要求任何锁匠解锁箱子。
示例输入 3
20 10 40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15 2 11 221 14 20 14 2 11 126 1 8 273 5 11 94 2 8 48 12 15 83 2 7 13 5 16 269 3 12 115
示例输出 3
760