Surf

Division 2 ACM ICPC programming problem. Time: 4 seconds.

Problem

Now that you’ve come to Florida and taken up surfing, you love it! Of course, you’ve realized that if you take a particular wave, even if it’s very fun, you may miss another wave that’s just about to come that’s even more fun. Luckily, you’ve gotten excellent data for each wave that is going to come: you’ll know exactly when it will come, how many fun points you’ll earn if you take it, and how much time you’ll have to wait before taking another wave. (The wait is due to the fact that the wave itself takes some time to ride and then you have to paddle back out to where the waves are crashing.) Obviously, given a list of waves, your goal will be to maximize the amount of fun you could have. Consider, for example, the following list of waves:

Minute	Fun Points	Wait Time
2	80	9
8	50	2
10	40	2
13	20	5

In this example, you could take the waves at times 8, 10 and 13 for a total of 110 fun points. If you take the wave at time 2, you can’t ride another wave until time 11, at which point only 20 fun points are left for the wave at time 13, leaving you with a total of 100 fun points. Thus, for this input, the correct answer (maximal number of fun points) is 110.
Given a complete listing of waves for the day, determine the maximum number of fun points you could earn.

Input

---

The first line of input contains a single integer n (1 ≤ n ≤ 300,000), representing the total number of waves for the day. The ith line (1 ≤ i ≤ n) that follows will contain three space separated integers: m_i, f_i, and w_i, (1 ≤ m_i, f_i, w_i ≤ 106), representing the time, fun points, and wait time of the ith wave, respectively. You can ride another wave occurring at exactly time m_i + w_i after taking the ith wave. It is guaranteed that no two waves occur at the same time. The waves may not be listed in chronological order

Output

---

Print, on a single line, a single integer indicating the maximum amount of fun points you can get riding waves.

Sample Input	Sample Output
4 8 50 2 10 40 2 2 80 9 13 20 5	110

Sample Input	Sample Output
10 2079 809484 180 8347 336421 2509 3732 560423 483 2619 958859 712 7659 699612 3960 7856 831372 3673 5333 170775 1393 2133 989250 2036 2731 875483 10 7850 669453 842	3330913

Solution

The key to solving this problem in a short period of time is to leverage principles of dynamic programming, and make use of efficient data structures.

Approach

---

At first glance, the problem structure resembles group interval scheduling maximization problem (GISMP). In these types of problems, the goal is to find the largest compatible set — a set of non-overlapping representatives of maximum size. In this scenario, a set of non-overlapping waves that produce the combined maximum points. It would seem as though to solve this problem one would store the maximums for each period of time up to the last waves start time, but this is not the case—at least in this implementation. Instead, maximums are stored for each new wave. There are two maximums of interest: actual and real. The actual maximum represents the highest accumulated point total for this wave and all subsequent non-overlapping waves that come before it assuming this wave is actually a member of the set. The real maximum represents the highest accumulated point total amongst all possible non-overlapping combinations of waves up to this wave regardless if this wave is included in the set of waves. Therefore, the real maximum for a particular wave may not include the wave as part of the total if there is a higher maximum total that can be achieved without it.

General Idea

---

The algorithm we choose to implement goes something like this:

1. For each line in the input data:
   1. Create a wave object (start time, fun points, and duration).
   2. Add this wave to an ArrayList of wave's.
2. Sort the ArrayList by the wave's start time (when the wave crashes).
3. For each wave in the list:
   1. Add this wave to a Priority Heap (lowest end time first).
   2. For each wave in the heap that ends (start time + duration) before this wave begins (non overlapping):
      1. Remove it from the heap.
      2. Compare its actual max against the local actual max.
      3. If its acutal max > local actual max ? update local actual max : continue
   3. Set the global actual max = local actual max
   4. Set this wave's actual max = its fun points + global actual max.
   5. If this wave's actual max > previous wave real max ? set this wave real max = its actual max :set this wave's real max = previous waves real max.
4. Return the last wave's real max.

Time

---

Can analyze input size of 300,000 waves and determine real max in 798 milli seconds.

---

2015 Pacific Northwest Region Programming Contest—Division 2