#P5816. [CEOI2017] Sure Bet

    ID: 4817 传统题 2000ms 256MiB 尝试: 3 已通过: 1 难度: 4 上传者: 标签>贪心数据结构排序与序列处理单调栈CF1600排序前缀和枚举

[CEOI2017] Sure Bet

题目描述

有一场只有两种结果的比赛和 nn 家博彩公司。第 ii 家对两种结果开出的赔率分别是 aia_i 和 bib_i。

每次下注花费 11 欧元。你可以在同一家下注两种结果,但对每家公司的每种结果最多下注一次。若某次下注猜中结果,就按赔率获得相应欧元,为第一种结果下注猜中时返还 aia_i,为第二种结果下注猜中时返还 bib_i。猜错时返还 00。无论结果如何,都要扣除此前所有下注的总费用。

你可以选择任意一组下注,也可以一注不下。求两种比赛结果均能保证的最大净收益,即最大化两种结果的净收益中的较小值。

输入格式

从标准输入读入数据。第一行一个整数 nn。接下来 nn 行,每行两个实数 ai,bia_i,b_i,最多有四位小数。

输出格式

向标准输出写入最大保证净收益,四舍五入后恰好保留四位小数。

样例 #1

样例输入 #1

4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5

样例输出 #1

0.5000

样例说明

在第 11 家为第二种结果下注,在第 33、44 家为第一种结果下注,总成本为 33 欧元。若第一种结果发生,净收益为 1.6+1.9−3=0.51.6+1.9-3=0.5 欧元。若第二种结果发生,净收益为 3.7−3=0.73.7-3=0.7 欧元。可以保证 0.50.5 欧元。

数据范围

1≤n≤1051\le n\le 10^5。1.0≤ai,bi≤1000.01.0\le a_i,b_i\le 1000.0。

原赛子任务 分值 附加限制
1 20 n≤10n\le10
2 40 n≤1000n\le1000
3 无