乡村现代化建设
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
最进,政府部门想要促进乡村现代化建设,大兴土木,又是修路,又是安装路灯等等,目前经费有点紧张,想要尽可能的节省经费做到最好的效果。
刚好有个安装路灯问题需要解决:
假设乡村每家每户都是以一条直线排列,而且每家有一个范围 [L, R] ,表示这家所占位置是在这条路的 L 到 R ,同时根据每家为政府部门的贡献不一,安装的路灯数目也不同(政府部门根据贡献并加以补偿作为此家安装路灯的经费), 假设路是一条坐标轴,路灯只能安装到整数下标上,每家安装路灯等总数必定小于等于 R - L + 1 ,即使贡献超过安装路灯总价值。
要求在有限的贡献内最小安装路灯的数量,达到每家每户的贡献要求。
输入格式
输入包含多行,第一行包含 3 个整数 N , P , Q ,分别表示这条路上居户的户数,政府部门补偿金额和安装一台路灯需要的金额数目。
接下来的 N 行每行输入 3 个整数 L , R, W ,表示这家居户所在位置和它的贡献(每家的 L R 可能存在交叉, 即 [2, 5] 和 [3, 6])。
输出格式
输出一行答案表示最少需要安装多少台路灯, 并换行输出政府收益(可能为正或负)。
数据范围
1 ≤ N, Q ≤ 10^5
0 ≤ P ≤ 10^9
1 ≤ L ≤ R ≤ 10^9
Q ≤ W ≤ 10^9
样例
样例输入
3 0 1
2 3 1
5 5 1
5 6 2
样例输出
3
1
解释
第一家居户:选择在 2 或 3 位置上安装路灯(总贡献 = 政府补贴 + 自己贡献 = 0 + 1 = 1, 可安装 ⌈总贡献 / Q⌉ = ⌈1 / 1⌉ = 1 台路灯 )
第二家居户:选择在 5 位置上安装路灯( ⌈(1 + 0) / 1⌉ = 1台 )
第三家居户:选择在 5、6 位置上安装路灯( ⌈(2 + 0) / 1⌉ = 2台 )
因此政府仅需在 2、5、6 或 3、5、6 三个位置安装路灯即可,保证安装数量最少
政府收益为:(1 + 1 + 2)- (3 * 1) = 1
样例输入
3 1 1
1 3 1
2 5 2
5 6 1
样例输出
4
0
解释
第一家居户:选择在 2、3 位置上安装路灯( ⌈(1 + 1) / 1⌉ = 2台 )
第二家居户:选择在 2、3、5 位置上安装路灯( ⌈(1 + 2) / 1⌉ = 3台 )
第三家居户:选择在 5、6 位置上安装路灯( ⌈(1 + 1) / 1⌉ = 2台 )
因此政府仅需在 2、3、5、6 四个位置安装路灯即可,保证安装数量最少
政府收益为:(1 + 2 + 1)- (4 * 1) = 0
温馨提示: 如果一家居户位于 [3, 5] ,此范围内最多安装 5 - 3 + 1 = 3 台路灯, 即使贡献超过三台路灯的价值;数据范围过大,请采用 long long。
时限: 300ms
出题人: dreamy-xay