#P8593. 「KDOI-02」一个弹的投
「KDOI-02」一个弹的投
题目背景
- 前置芝士:平抛运动
(看到这个如果不想做可以直接开下一题)
「这群该死的外星人,肯定是来抢夺新矿资源的!」
「这导弹什么鬼啊,研究不明白。」
无数的水滴型武器从苍穹之外落下,猛击着无知的生命。
题目描述
经研究,该武器的运作方式是这样的。其中设重力方向为 轴负半轴, 轴为地面,速度向右为正向左为负。
- 每颗导弹在 的地方投放并悬浮,初始速度设置为 。
- 所有导弹投放完成后,于同一时刻开始照初始速度做平抛运动。其中 。
- 每颗导弹与另一颗导弹碰撞时,不会改变原来的路线,并且将爆破威力 增加 ,所有导弹初始时 ,在接触到 轴时碰撞也增加威力。
- 当武器落到 轴时,会对落点造成 点杀伤力。
地面指挥部提前预测了导弹的落点,并部署了反制武器。第 台武器能将第 枚导弹在降落至地面后的威力值减少 (至多减少到 )。但是,由于技术限制,只能启动其中 台反制武器。地面指挥官想知道,导弹造成的爆炸威力值总和最小为多少。
输入格式
从标准输入中读入数据。
输入一共包含 行。
第 行输入两个正整数 。
第 行到第 行每行包含三个整数 ,表示第 颗导弹的起点坐标和水平速度。
第 行包含 个非负整数 ,含义见题目描述。
输出格式
输出到标准输出。
输出一行一个非负整数,表示答案。
3 0
1 1 -2
1 2 -1
1 3 1
1 1 1
0
4 1
-3 3 0
1 3 1
4 3 -4
-9 3 -7
1 3 2 3
1
见附件中的 missile3.in
见附件中的 missile3.ans
见附件中的 missile4.in
见附件中的 missile4.ans
提示
【样例解释】
-
样例 1 解释:
每颗导弹的爆炸威力值都是 。
-
样例 2 解释:
四枚导弹的爆炸威力值分别是 ,启动第 或第 台反制武器,最后爆炸威力值的和为 。
-
样例 4 说明:
该样例满足测试点 的限制。
【数据范围】
对于 的数据,,,,。
保证所有导弹起始坐标不相等。
测试点编号 | 特殊性质 | |
---|---|---|
无 | ||
有 | ||
无 | ||
特殊性质:保证所有 均相同。
【提示】
本题 I/O 量较大,推荐使用较快的 I/O 方式。
附平抛运动落点公式: