「EVOI-RD1」马戏团
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目背景
WuuTue拥有一家马戏团，马戏团会在全国巡演，最近WuuTue的马戏团来到了T市。
题目描述
T市有一条专门的演出街，演出街是一条东西走向的笔直街道，街道上从西往东有 个舞台，舞台的编号为 。
WuuTue计划在T市的演出街上进行 场演出，其中第 场演出要占用从 到 的连续舞台（包括 和 ），同时WuuTue知道，第 场比赛将会获得 元的收益。
由于演出街的舞台都是设计给人表演使用的，如果要供动物表演使用的话，需要进行加固，其中加固第 个舞台需要花费 元钱，并且只需要加固一次，可以重复使用。也就是说如果有多个演出都用到了舞台 ，那么只需要花费一次加固的费用就可以了。
当然，如果WuuTue发现某场演出可能由于加固费用过高无法盈利，也可能会取消演出。
因为WuuTue太蒻了，所以请帮助WuuTue计算，他最多可以获得多少元钱的收入。
输入格式
第一行：两个空格分隔的整数 和 ，分别表示舞台和演出的数量。
第二到 行：每行 个整数，其中第 行的整数表示加固第 个舞台需要的花费 。
第 行到第 行：每行 个空格分隔的整数，其中第 行的 个整数 ，，，表示第 场演出需要占用第 到 的连续舞台，可以获得 元的收益。
输出格式
一行：一个整数，表示WuuTue可以获得的最大收益。
7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5
4
2 1
0
3
1 2 5
2
3 1
10
10
10
1 3 10
0
提示
本题采用捆绑测试
对于 的数据， 。
另有 的数据， 。
另有 的数据， 。
对于 的数据， $1 \le n , m \le 10^6 , 0 \le v_i , c_i \le 10^9 , 1 \le l_i \le r_i \le n$。
国庆提高组30题(1~3号)
- Status
- Done
- Rule
- IOI
- Problem
- 28
- Start at
- 2024-9-29 17:00
- End at
- 2024-10-8 1:00
- Duration
- 200 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 55