TROOPS - Troops of Sand Monsters
Under the command of the Evil Vizier there are N unique troops of sand monsters, where each troop contains Ci sand monsters. The Vizier in his desperate battle against the Prince of Persia has ordered all his troops to attack him simultaneously.
The Prince realizes that he cannot defeat all of the sand monsters, as they are invincible when they are active. So he uses the Eye of the Storm spell to freeze all the sand monsters of all troops. Now the Prince can kill any monster by stabbing each monster once using the Dagger of Time. Once the monster is killed, it can never become active again and releases a certain quantity of the Sands of Time. It takes one unit of time to kill any monster.
Each troop i, consits of Ci similar monsters, all with the same spell resistance time Ti - after which it becomes active again and therefore invulnerable - and Sand Si - which can be taken by the Prince after killing it.
The spell lasts only for a limited duration of time. So, the Prince has to kill as many sand monsters as possible and take maximum sand from the monsters before they become active again. It is not necessary for The Prince to kill all the monsters in a troop before moving on to next troop.
The first line contains K <=70 the number of testcases. Each testcase begins with 'N' (<=1000) the number of troops of monsters. Next N lines contain 3 integers Ci, Ti, Si. 1<i<=N, 1<=Ci<=15000, 1<=Ti<=1000000, 1<=Si<=100,
Single Line containing the maximum amount of sand that Prince can get if he kills some or all the monsters.
2 1 2
2 3 6
2 5 5
2 7 8
Explanation(time, troop, sand)
(0,1,2) (1,2,6) (2,2,6) (3,3,5) (4,3,5) (5,4,8) (5,4,8) = 40
the tag for this problem is misleading..
i'm getting TLE, my complexity is O(max(Ti)*k), what is the expected complexity??Last edit: 2015-09-04 22:42:33
What's the solution for test case
does prince has to kill at least one monster from all the troops or there be a case where he can leave a troop as it is?
In addition to the problem statement:
WA.. can u give me some tricky tests??
It seems that the Prince is skilled enough to avoid attacks from awakened monsters :). You can kill any number of monsters in any order. You have to leave the second one from the first troop in the test case, because it will be active after you stab the first one.
~ adieus ~:
I think there is a mistake in your explanation your have (5,4,8) twice ? is the last one supposed to be (6,4,8) ?