TLE '17 Contest 8 P2 - Ship Defense

View as PDF

Submit solution



Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:

Problem type

Fax McClad attacked by enemy ships.

Fax McClad, Croneria's most defensive bounty hunter, is under attack by the Dankey Kang Gang! He must activate certain defense modes on his personal ship, the Kyuwing, in order to prevent as much damage as possible.

Fax's Kyuwing has H health points and is equipped with D defense modes. Each defense mode has an armor and shield component. Every second, shields block up to S_i of the incoming damage while armor reduces the remaining damage by A_i\%. At any given time, at most one defense mode can be activated, and defense modes can be reactivated.

There are E enemy ships that each shoot at Fax's Kyuwing over the course of the battle. Enemy ship j deals X_j damage for L_j seconds starting at the T_j^{th} second. Note that at any second, the incoming damage is the total damage from all sources at that second.

Since repairs can be quite expensive, Fax wants to optimally choose defense modes to activate in order to reduce the amount of damage he receives. Can you tell him the maximum amount of health points that his ship can have after these enemy encounters?

Input Specification

The first line contains three space-separated integers: H (1 \le H \le 10^8), D (0 \le D \le 5), and E (0 \le E \le 1\,000).

D lines of input follow. The i^{th} line contains A_i (0 \le A_i \le 100) and S_i (0 \le S_i \le 10\,000).

E lines of input follow. The j^{th} line contains T_j (0 \le T_j \le 500), L_j (1 \le L_j \le 500), and X_j (1 \le X_j \le 50).

Output Specification

The maximum amount of health points that Fax's ship can have remaining, rounded to two decimal places.

If Fax's ship cannot sustain all of the damage, that is, his Kyuwing's health points become 0, then output: DO A BARREL ROLL!

Sample Input 1

100 2 2
50 0
0 10
0 10 11
5 1 50

Sample Output 1

60.50

Explanation 1

Fax should utilize defense mode 1 during the fifth second.

During all other times, Fax should switch to the defense mode 2 in order to block more of the incoming damage.

Sample Input 2

10 1 1
50 10
3 1 50

Sample Output 2

DO A BARREL ROLL!

Comments

There are no comments at the moment.