思考题 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