#P4141. [thoi2013]魔塔

    ID: 3357 传统题 1000ms 512MiB 尝试: 18 已通过: 3 难度: 8 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举数论整除分块数值计算与优化凸性/单峰性判定计算几何扫描线模拟与实现技巧增量维护CF2400

[thoi2013]魔塔

[THOI 2013] 魔塔

题目描述

沫沫要为勇士购买初始生命值、攻击力和防御力。在进入魔塔后,勇士必须击败 NN 只怪物才能救出公主。

每次战斗中,勇士和怪物每秒同时攻击对方一次,给对方造成的伤害为自己的攻击力减去对方的防御力,差为负时伤害为 00。至少一方生命值降为 00 或更低时战斗结束。勇士必须能在有限回合内结束战斗,而且结束时自己的生命值仍为正。勇士保留剩余生命值进入下一场战斗,攻击力和防御力始终保持初始值。

每点初始生命值、攻击力和防御力分别花费 11、CaC_a 和 CdC_d 枚金币。勇士的三项初始属性均须为正整数。可以自行安排挑战怪物的顺序,求能击败所有怪物且总花费最少的一组初始属性。

输入格式

第一行三个正整数 N,Ca,CdN,C_a,C_d(1≤N≤5 0001\le N\le5\,000,1≤Ca,Cd≤1061\le C_a,C_d\le10^6)。接下来 NN 行,第 ii 行三个正整数 Hi,Ai,DiH_i,A_i,D_i(均不超过 10610^6),分别表示第 ii 只怪物的生命值、攻击力和防御力。

输出格式

输出一行三个正整数,依次为勇士的初始生命值、攻击力和防御力。如果有多种最优方案,输出任意一种。

样例 #1

样例输入 #1

3 2 5
5 30 5
20 10 3
100 5 1

样例输出 #1

41 10 5

样例说明

按输入顺序战斗时,勇士依次用 11、33 和 1212 秒击败三只怪物,损失的生命值分别是 2525、1515 和 00。勇士最后剩余 11 点生命值,初始属性花费 41+2×10+5×5=8641+2\times10+5\times5=86 枚金币。