#2181. 赌徒
赌徒
赌徒
题目描述
标题: 赌徒 - Problem - QOJ.ac
#8348. 赌徒
The problem was used in the following contests:
题目描述
萌新小 H 和他的 n 个好朋友玩游戏!
他们将要玩的游戏是抛硬币,小 H 和他的对手分别抛出硬币,如果小 H 抛出的数值大于等于对方的,则小 H 赢,否则对手赢。
第 i 个好朋友有一个两面分别为 ai 和 bi 的硬币,他和小 H 赌 xi 个钢镚,即如果小 H 赢则他获得 xi 个钢镚,否则失去 xi 个钢镚。
小 H 还没有硬币,它可以去邪恶工匠大 D 定制一枚硬币。若小 H 得到的硬币两面分别是 a,b,则 a,b 都需要是正整数,并且他需要支付 ab 个钢镚。
小 H 想知道,如果他选择一枚合适的硬币,他期望最多能挣到多少钢镚。
注意小 H 很富有,他初始有足够多的钢镚,不需要考虑钢镚不足以支付的情况。
输入格式
第一行一个整数 n 表示好朋友个数。
接下来 n 行每行三个整数 ai,bi,xi 分别表示对手硬币两面的数字和赌资。
输出格式
一行一个整数,表示小 H 期望挣到的钢镚乘上 4 后的结果,可以证明这一定是一个整数。注意亏钢镚被认为是挣了负数个钢镚。
样例一
input
2
1 4 15
3 5 10
output
10
explanation
造的硬币两面分别是 1,5。
样例二
input
1
2 2 8
output
16
数据范围与提示
子任务编号 n≤ 特殊性质 分值 1 100 无 3 2 2000 无 21 3 5×105 ai,bi,xi 在 [1,109] 中随机生成 34 4 5×105 无 42
对于所有数据,保证 1≤n≤5×105,1≤ai,bi,xi≤109。
时间限制:2s
空间限制:512MB
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
1 4 15
3 5 10
10
样例 2
1
2 2 8
16