Mighty Cactus

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem types

hiddencactus has some amazing super powers! One day, he was in the desert, fighting off bad guys. The battle got very serious, and he needs your help to win the battle!

hiddencactus has K different sets of plant armor, and each of the armor has 3 sets of properties.

  • t_i, the toughness of the armor, which reduces the incoming damage by t_i
  • a_i, the shock absorption of the armor, which reduces the remaining damage by a_i \%
  • At any given time, at most one plant armor can be used, and plant armors can be reused.

There are M enemies and they all have a set duration of attack, for each enemy:

  • They have a start time s_i, representing the start time of the attack in seconds.
  • They have a duration of attack, which is l_i, which means the enemies damage hiddencactus up to the s_i + l_i-1 second, starting from the s_i^{th} second.
  • They have an attack damage, x_i, meaning enemies do x_i points of damage every second that they are attacking.

hiddencactus starts with N health points, meaning that he can take up to N points of attack damage.

hiddencactus is concentrating on the battle, and is confused on the optimal usage of his armor, can you help him? You are to help him find the maximum amount of health points he has left, if he uses his plant armors optimally.

Input Specification

The first line contains the 3 integers N (1 \le N \le 10^9), M (0 \le M \le 10^5) K (0 \le K \le 5), denoting the number of health points, enemies, and armor sets respectively.

The next K lines each contain two integers, t_i (0 \le t_i \le 2 \times 10^6) and a_i (0 \le a_i \le 100).

The next M lines each contain three integers, s_i (0 \le s_i \le 10^5), l_i (1 \le l_i \le 10^5) and x_i (1 \le x_i \le 100).

Output Specification

The maximum amonut of health points hiddencactus can have remaining, rounded to two decimal places.

If hiddencactus cannot sustain all the damage, you are to output Act Like A Cactus..

Sample Input 1

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

Sample Output 1


Explanation Of Sample 1

hiddencactus should use plant armor #1 during the fifth second.

During all other times, he should use plant armor #2 to block more of the incoming damage.

Sample Input 2

10 1 1
10 50
3 1 50

Sample Output 2

Act Like A Cactus.


There are no comments at the moment.