思考题 greedy?

# SMM

Have you ever played Super Mario Maker (2)? There's an interesting mode called *Endless Challenge*. Let's look at a simplified version:

The game contains N levels. The player plays from level 1 to level N in order. In Level i, there are Ai 1-UP mushrooms and Bi coins. When player collects one 1-up mushrooms, he will gain one extra life. When player collects 100 coins, it will be converted into a 1-up mushroom **at the exact moment**. One cannot gain more than 3 lifes in a level. Moreover, the player have 0 lifes at first.

After beating these N lifes, each life will be converted into 1 point, each coin will be converted into 0.01 point. Assume the player plays well enough and never lose life. What's the maximum point you will get?

# Example

Input:

A={1,2,3}

B={10,100,120}

Output: 7.30

Explain:

In level one, we collect 1 1-up mushroom and 10 coins, now Life=1 Coin=10

In level two, we collect 2 1-up mushrooms and 100 coins. The first 90 coins altogether with the coins we collected in the first level convert to 1 life, now Life=4 Coin=10

In level three, we collect 3 1-up mushrooms and 120 coins. The first 90 coins altogether with the coins we have convert to 1 life. But we've already gained 3 lifes in this level by collecting 1-up mushrooms, so these lives don't count. Now life=7 Coin=30

Input 2:

A={3,2}

B={100,100}

Output 2:1.99

Explain 2:

We collect 99 coins in the first level and 100 in the second.

If you collect 100 coins in the first level, the answer is 1.00 which is worse.

# Constraints

Subtask 1(30%): N<=1000

Subtask 2(30%): N<=10000

Subtask 3(30%): N<=100000

Subtask 4(10%): N<=1000000

# Solution

DP works to subtask 2. I wonder if we can cheese by greedy