luogu#P4985. 反射

    ID: 9009 远端评测题 3000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>O2优化期望图的建立建图搜索

反射

题目背景

最近 TimeTraveller \rm \ TimeTraveller\ 玩了一个十分好玩的游戏,通过摆放能量发射器,来攻击敌人的飞船。

但是 TimeTraveller \rm \ TimeTraveller\ 十分手残以及脑残,总是玩不过十分简单的关卡,所以他想请你帮助他。

题目描述

这个游戏是这样的,你有kkα\alpha能量发射器启动器,可以启动任何kk个在一个初始平台上α\alpha发射器,然后α\alpha发射器会向北偏东4545^\circ方向上发射能量光束,能量值为αi\alpha_i。在有场地里面有nn块悬浮的平台,这些平台上有的装有两种能量发射器α\alpha发射器和β\beta发射器的其中一种,功能如下:

  • 对于α\alpha发射器,如果它装在平台上方,它会向北偏东4545^\circ方向上发射能量光束,能量值为αi\alpha_i;如果装在下方,它会向南偏东4545^\circ方向上发射能量光束,能量值为αi\alpha_i

  • 对于β\beta发射器,不管装在什么地方它会同时向北偏东4545^\circ和南偏东4545^\circ发射能量光束,能量值为βi\beta_i

但是,悬浮平台上的发射器并不会自己启动,必须在有能量光束击中它所在的平台上时才会启动,且这个发射器发射的能量为给定的值(注意一束光击中这些平台,只有在这个能量光束的来的路径上没有该击中平台提供的能量时这些平台的发射器就会启动,每被击中一次就发射一次,如下图,1号发射给2号2号激活,其中一个击回1号,此时1号不会再发射一次(也就是能量不会再次叠加))

你在最开始只能启动初始平台上的能量发射器中的kk个(这kk个是依次启动的,且每个只能发射一次,但是其它地方的发射器可以发射多次)。

将地图抽象为二维平面直角坐标系,其中x=0x=0的直线为地面(光束到达地面会消失,但是如果地面有平台则优先击中平台),那么所有的平台包括初始平台均平行于xx轴,敌人的飞船可以看做为一个平行于yy轴的,两个端点为(wx,sy)(wx,sy)(wx,ty)(wx,ty),当一条光束击中飞船它便会受到光束来的这条路径上的所有能量值的和的伤害然后光束就会消失。(光束击中其它平台并不会反弹,而是会被平台吸收作为能量来启动发射器)。

请你求出在启动哪些开始的α\alpha发射器,使得让飞船受到的伤害最大,请你求出这个最大值。

输入格式

第一行两个正整数k,nk,n,表示你能启动kk个开始的发射器,总共有nn个平台。 第二行四个整数x1,x2,y,vx_1,x_2,y,v,表示初始平台位置,初始平台上每一个整点有一个α\alpha发射器能发射初始能量为vv的能量光束(如x1=1,x2=3,y=1x_1=1,x_2=3,y=1时,有(1,1),(2,1),(3,1)(1,1),(2,1),(3,1)三个初始位置的α\alpha发射器)。 第三行三个整数wx,sy,tywx,sy,ty,表示敌人飞船位置。 下面nn行,每行描述了一个平台,格式如下:

  • 0 xl xr y0\ x_l\ x_r\ y表示一个空的平台
  • 1 xl xr y xp wi 0/11\ x_l\ x_r\ y\ x_p\ w_i\ 0/1表示在(xp,y)(x_p,y)的位置一个α\alpha发射器在(xl,y)(xr,y)(x_l,y)\sim (x_r,y)的平台上,发射能量为wiw_i,最后的0011表示在平台的上方还是下方,00为上方,11为下方。
  • 2 xl xr y xp wi2\ x_l\ x_r\ y\ x_p\ w_i表示在(xp,y)(x_p,y)的位置一个β\beta发射器在(xl,y)(xr,y)(x_l,y)\sim (x_r,y)的平台上,发射能量为wiw_i

输出格式

一行一个整数表示最大的伤害值。

1 3
1 2 1 5
8 1 7
1 4 5 3 5 5 0
2 4 5 5 5 5
1 5 6 6 6 5 1

25
1 11
0 2 1 10
17 3 11
0 1 2 6
1 3 5 5 4 30 0
1 4 7 4 6 10 1
2 4 8 7 6 14
1 7 10 2 9 10 0
1 8 11 10 9 14 1
1 11 13 7 12 10 0
2 11 13 5 12 14
1 11 13 1 12 10 0
2 13 14 8 14 6
1 13 15 3 14 10 0

242

提示

样例解释:

样例11如图:

最优为橙色那个2525,绿色的为1010

样例22如图:

只有橙色那条打出来为242242,其他两条只有9898

数据范围:

  • 对于30%30\%的数据0n20,1k30\leq n\leq 20,1\leq k\leq 3

  • 对于40%40\%的数据所有平台(不包括飞船)的长度和不超过10610^6

  • 对于60%60\%的数据0n200,1k500\leq n\leq 200,1\leq k\leq 50

  • 对于70%70\%的数据0n2000,1k20000\leq n\leq 2000,1\leq k\leq 2000

  • 对于100%100\%的数据0n20000,0k200000\leq n\leq 20000,0\leq k\leq 20000,坐标0y1090 \leq y\leq 10^9的,坐标0x1090\leq x\leq 10^9,所有的能量值的值均在01040\sim 10^4内,且保证每个发射器必定在一个平台上,且平台长度与敌人飞船的长度大于等于11。保证最开始的平台长度不超过10510^5,且所有的平台不会重叠;

  • 还有20%20\%的额外数据同100%100\%,只是n106n\leq 10^6

输入较大,建议使用较快的读入方式。