DMOPC '15 Contest 2 P4 - Personal Assistant

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem types

You have just been hired as FatalEagle's personal assistant! In addition to doing his math homework and writing his essays for him, your job description also includes planning out his anime marathons.

On this particular day, N animes will be released. The i-th anime is released on the R_i-th minute and is L_i minutes long (1 \le i \le N). FatalEagle likes to watch animes as soon as they are released and he doesn't like to stop halfway through an episode to switch to another anime, this means that he will only watch the i-th anime at the R_i-th minute, and if he does, he will not be able to watch any animes that start in the following L_i - 1 minutes. Having done your research online, you were also able to designate each of the animes a value H_i, the happiness that the i-th anime will bring your employer.

Since you want to make FatalEagle as happy as possible, find the maximum possible happiness he can have if you plan his anime marathon optimally.


Subtask 1 [20%]

1 \le N, L_i, H_i \le 100

R_i = i

(See Sample Input 1)

Subtask 2 [50%]

1 \le N, R_i, L_i, H_i \le 10^5

(See Sample Input 2)

Subtask 3 [30%]

1 \le N \le 10^5

1 \le R_i, L_i, H_i \le 10^{12}

(See Sample Input 3)

Warning: Fast I/O is highly recommended and even necessary for slower languages such as Java and Python. Check here for details.

Input Specification

The first line of input contains integer N, the number of animes being released.

The i+1-th line contains integers R_i, L_i and H_i, the release time, length and happiness value of the i-th anime, respectively. It is guaranteed that animes are given in non-decreasing order of R_i.

Output Specification

One integer, the maximum amount of happiness possible for FatalEagle if you plan his marathon optimally.

Sample Input 1

1 2 3
2 1 5
3 1 3
4 2 4
5 1 5

Sample Output 1


Explanation for Sample Output 1

If FatalEagle always watches the next anime he can, he will watch animes 1, 3, and 4, leading to a total happiness value of 3+3+4 = 10. The optimal plan is to skip anime 1, watch 2 and 3, skip 4, and watch 5, yielding the maximum possible happiness value of 5+3+5 = 13.

Sample Input 2

1 5 6
1 3 4
1 7 5
4 10 3

Sample Output 2


Explanation for Sample Output 2

The optimal plan is to watch animes 2 and 4.

Sample Input 3

1 1000000000000 1000000000000
99999 99999 99999
123456 789 101112
416647 1333337 1000000000
416647 1 9988776655
99999999999 99999999999 99999999999

Sample Output 3


Explanation for Sample Output 3

Although anime 1 requires tons of time investment, it's so good that FatalEagle will be content with only watching that anime.


There are no comments at the moment.