UOJ Logo LFYZ Online Judge

LFYZOJ

#91. 经营与开发

统计

问题描述

4X 概念体系,是指在 PC 战略游戏中一种相当普及和成熟的系统概念,得名自 $4$ 个同样以“EX”为开头的英语单词。

eXplore(探索)

eXpand(拓张与发展)

eXploit(经营与开发)

eXterminate(征服)

——维基百科

今次我们着重考虑 exploit 部分,并将其模型简化:

你驾驶着一台带有钻头(初始能力值 $w$)的飞船,按既定路线依次飞过 $n$ 个星球。

星球笼统的分为 $2$ 类:资源型和维修型。($p$ 为钻头当前能力值)

  1. 资源型:含矿物质量 $a_i$,若选择开采,则得到 $a_i \times p$ 的金钱,之后钻头损耗 $k\%$,即 $p \leftarrow p \times (1-0.01k)$。
  2. 维修型:维护费用 $b_i$,若选择维修,则支付 $b_i \times p$ 的金钱,之后钻头修复 $c\%$,即 $p \leftarrow p \times (1+0.01c)$。

注:维修后钻头的能力值可以超过初始值(你可以认为是翻修+升级)。

请作为舰长的你仔细抉择以最大化收入。

输入格式

第一行 $4$ 个整数 $n,k,c,w$。

以下 $n$ 行,每行 $2$ 个整数 $\texttt{type},x$。

$\texttt{type}$ 为 $1$ 则代表其为资源型星球,$x$ 为其矿物质含量 $a_i$;

$\texttt{type}$ 为 $2$ 则代表其为维修型星球,$x$ 为其维护费用 $b_i$。

输出格式

一个实数(保留 $2$ 位小数),表示最大的收入。

样例一

input

5 50 50 10
1 10
1 20
2 10
2 20
1 30

output

375.00

数据范围与约定

对于 $30\%$ 的数据,$n \leq 100$。

另有 $20\%$ 的数据,$n \leq 1000$,$k=100$。

对于 $100\%$ 的数据,$n \leq 100000$,$0 \leq k,c,w,a_i,b_i \leq 100$。

保证答案不超过 $10^9$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$