TJ monthly 图灵姬月赛 2020.1

1004. Zeratul与塔防游戏

时间限制: C/C++/Pascal 1500 ms; Others 3000 ms

内存限制: 256 MB

题目描述:

Zeratul有 n 座防御塔,每个防御塔覆盖 [L[i],R[i]] ,且攻击力为 A[i]

区间 [1,m] 上每个整点有一个防御值,是所有能覆盖到这个点的防御塔的攻击力之和。

Zeratul可以给防御塔升级 k 次,每次升级可以将一个防御塔的攻击力提高 1 。同一个防御塔可以被多次升级。

现在Zeratul想知道, [1,m] 上所有整点的最小防御值最大是多少。

输入格式:

第一行包括三个整数 n,m,k ,含义见题目描述。 接下来 n 行,每行包括三个整数 L[i],R[i],A[i] ,代表第 i 座防御塔的覆盖范围和第 i 座防御塔的攻击力。

输出格式:

一个整数,代表最小的防御值最大是多少。

样例:

Input
Copy
3 5 3
1 4 5
2 5 1
3 4 1
Output
Copy
4

数据范围及提示

对于10%的数据, n=1

对于另外10%的数据, k=0

对于40%的数据, n \le 10, k \le 5, m \le 20

对于另外20%的数据, L[i]=R[i]

对于80%的数据, n \le 10000,m \le 10000

对于100%的数据, 1 \le n \le 1000000,1 \le m \le 1000000,1 \le A[i] \le 1000,1 \le L[i] \le R[i] \le m,0 \le k \le 10^9

已结束

积分

题目 计分
1001 100
1002 100
1003 100
1004 100
这里显示的是你在现在一次提交正确所获得的计分。
题目信息

题目类型:传统题

文件IO

输入文件名:tdgame.in

输出文件名:tdgame.out

AMAZE UI
Hello world!