시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 17 | 5 | 5 | 31.250% |
Nudgémon GO is a game in which players should earn as much experience points (XP) as possible, by catching and evolving Nudgémon. You gain 100 XP for catching a Nudgémon and 500 XP for evolving a Nudgémon. Your friend has been playing this game a lot recently, but you believe that his strategy is not optimal.
All Nudgémon are split into families, each of which has its own unique type of candy. The Nudgémon in a family are ranked from weakest to strongest and hence form a chain. Any Nudgémon that is not the strongest from its family can be evolved to the next ranked Nudgémon from the same family.
Candies are a fundamental currency in the Nudgémon universe:
Every evolution of a Nudgémon consumes a specific amount of its family’s kind of candy. Furthermore, the costs of evolutions along the family chain are non-decreasing, meaning that higher-ranked evolutions in the family will cost the same or more as lower ones.
Here is an example of possible Nudgémon evolutions:
Apart from making the developers money and nudging ’em all, the goal of this game is to earn as much XP as possible to level up the player’s character and be able to encounter stronger Nudgémon in the wild. As such, coinciding with the first goal, you can buy a Blessed Egg with real money in the game. This item allows you to double your earned XP for the next 30 minutes since activation, i.e. when the Egg is activated at time e (in seconds since the start of the game), for any action taken on time t, you will earn double XP if and only if e ≤ t < e + 1800.
At the start of the game your friend received a single Blessed Egg. Unfortunately, he completely wasted it. You believe that it is better to only evolve Nudgémon while the Blessed Egg is active, otherwise it is a huge waste of resources! To prove your point to your friend, you took a log of all Nudgémon he caught with timestamps and decided to calculate the maximum amount of XP he could have had right now if he was strategic about when to activate his Blessed Egg and only evolved Nudgémon during the time it was active.
The input consists of:
It is guaranteed that there are at most 105 Nudgémon kinds (Σi si ≤ 105 ). The Nudgémon in each family are given in order of increasing rank, and thus the values of c in one family are non-decreasing. Every Nudgémon name is a string of between 1 and 20 lowercase letters. The times ti are non-decreasing (your friend is so quick he can catch multiple Nudgémon in a single second). No Nudgémon name appears more than once within a family or within more than one family, and all n Nudgémon that are caught belong to one of the families.
Output the maximum amount of XP your friend could have had at the current time had he activated his Blessed Egg at the optimal time and only evolved Nudgémon during the time it was active.
3 3 caterpillar 3 pupa 7 butterfly 3 dove 3 pigeon 7 aaabaaajss 3 mouse 1 electromouse 5 rat 7 0 electromouse 500 electromouse 1000 electromouse 1500 rat 2000 aaabaaajss 2500 pigeon 3000 butterfly
5100
1 1 slownudge 2 0 slownudge 1800 slownudge
300
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2016 G번