#P8593. 「KDOI-02」一个弹的投

    ID: 7697 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>数学线段树树状数组2022洛谷原创O2优化

「KDOI-02」一个弹的投

题目背景

  • 前置芝士:平抛运动 (看到这个如果不想做可以直接开下一题)

「这群该死的外星人,肯定是来抢夺新矿资源的!」
「这导弹什么鬼啊,研究不明白。」
无数的水滴型武器从苍穹之外落下,猛击着无知的生命。

题目描述

经研究,该武器的运作方式是这样的。其中设重力方向为 yy 轴负半轴,xx 轴为地面,速度向右为正向左为负。

  • 每颗导弹在 (xi,yi)(x_i,y_i) 的地方投放并悬浮,初始速度设置为 viv_i
  • 所有导弹投放完成后,于同一时刻开始照初始速度做平抛运动。其中 g=9.8g=9.8
  • 每颗导弹与另一颗导弹碰撞时,不会改变原来的路线,并且将爆破威力 pip_i 增加 11,所有导弹初始时 pi=0p_i=0在接触到 xx 轴时碰撞也增加威力
  • 当武器落到 xx 轴时,会对落点造成 pip_i 点杀伤力。

地面指挥部提前预测了导弹的落点,并部署了反制武器。第 ii 台武器能将第 ii 枚导弹在降落至地面后的威力值减少 aia_i(至多减少到 00)。但是,由于技术限制,只能启动其中 mm 台反制武器。地面指挥官想知道,导弹造成的爆炸威力值总和最小为多少。

输入格式

从标准输入中读入数据。

输入一共包含 n+2n+2 行。

11 行输入两个正整数 n,mn,m

22 行到第 n+1n+1 行每行包含三个整数 xi,yi,vix_i,y_i,v_i,表示第 ii 颗导弹的起点坐标和水平速度。

n+2n+2 行包含 nn 个非负整数 a1,a2,,ana_1,a_2,\cdots,a_n,含义见题目描述。

输出格式

输出到标准输出。

输出一行一个非负整数,表示答案。

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 解释:

    每颗导弹的爆炸威力值都是 00

  • 样例 2 解释:

    四枚导弹的爆炸威力值分别是 0,1,1,00,1,1,0,启动第 22 或第 33 台反制武器,最后爆炸威力值的和为 11

  • 样例 4 说明:

    该样例满足测试点 131613\sim16 的限制。


【数据范围】

对于 100%100\% 的数据,1n5×1051\le n\le5\times10^50ai,mn0\le a_i,m\le n0xi,yi1090\le |x_i|,y_i\le10^90vi1060\le |v_i|\le10^6

保证所有导弹起始坐标不相等。

测试点编号 nn\le 特殊性质
161\sim6 50005000
7107\sim10 1200012000
111211\sim12 10510^5
131613\sim16
172017\sim20 5×1055\times10^5

特殊性质:保证所有 yiy_i 均相同。

【提示】

本题 I/O 量较大,推荐使用较快的 I/O 方式。

附平抛运动落点公式:

xt=xi+vi2yigx_t=x_i+v_i\sqrt{\dfrac{2y_i}g}