#P3203. [Sdoi2013]保护出题人

    ID: 2379 传统题 1000ms 512MiB 尝试: 1134 已通过: 444 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理一维前缀和计算几何凸包单调栈叉积二分查找数值计算与优化浮点补偿求和CF2300

[Sdoi2013]保护出题人

[SDOI2013] 保护出题人

题目描述

僵尸沿一条直路接近铭铭的房子。你要在房门前放置植物,保证每一关的所有僵尸都能及时被消灭。

第 ii 关共有 ii 只僵尸,从队首到队尾的血量依次为 ai,ai−1,…,a1a_i,a_{i-1},\ldots,a_1。开始时,队首距离房子 xix_i 米,相邻僵尸相距 dd 米,所有僵尸同时以每秒 11 米的速度向房子移动。你可以为这一关选择每秒造成 yiy_i 点伤害的植物。

植物从这一关开始时攻击最靠近房子的存活僵尸。子弹飞行时间忽略不计,每杀死一只就立刻转去攻击下一只。为了守住房子,每只僵尸受到的累计伤害必须在它到达门前时达到其血量。

求能守住全部 nn 关时,攻击力总和 ∑i=1nyi\sum_{i=1}^n y_i 的最小值。

输入格式

第一行包含两个正整数 n,dn,d,表示关数和相邻僵尸间的距离。

接下来 nn 行,第 ii 行包含两个正整数 ai,xia_i,x_i,分别表示第 ii 关新增的队首僵尸的血量和起始距离。

保证 1≤n≤1051\le n\le 10^5,1≤d,ai,xi≤10121\le d,a_i,x_i\le 10^{12}。

输出格式

输出一行一个整数,表示所求最小总和四舍五入到个位后的结果。若小数部分恰好等于 0.50.5,向上取整。

5 2
3 3
1 1
10 8
4 8
2 3
7

样例解释

关卡 从队首到队尾各僵尸的起始距离 从队首到队尾各僵尸的血量 最小攻击力(近似值)
11 33 1.000001.00000
22 1,31,3 1.333331.33333
33 8,10,128,10,12 10,1,310,1,3 1.250001.25000
44 8,10,12,148,10,12,14 4,10,1,34,10,1,3 1.400001.40000
55 3,5,7,9,113,5,7,9,11 2,4,10,1,32,4,10,1,3 2.285712.28571

最小总和约为 7.269057.26905,四舍五入后为 77。

相关

在下列比赛中:

三分