Mini Metro
Contest: Codeforces Round 497 (Div. 1)
Difficulty rating: 3400
Tags: dp

In a simplified version of a "Mini Metro" game, there is only one subway line, and all the trains go in the same direction. There are $$$n$$$ stations on the line, $$$a_i$$$ people are waiting for the train at the $$$i$$$-th station at the beginning of the game. The game starts at the beginning of the $$$0$$$-th hour. At the end of each hour (couple minutes before the end of the hour), $$$b_i$$$ people instantly arrive to the $$$i$$$-th station. If at some moment, the number of people at the $$$i$$$-th station is larger than $$$c_i$$$, you lose.

A player has several trains which he can appoint to some hours. The capacity of each train is $$$k$$$ passengers. In the middle of the appointed hour, the train goes from the $$$1$$$-st to the $$$n$$$-th station, taking as many people at each station as it can accommodate. A train can not take people from the $$$i$$$-th station if there are people at the $$$i-1$$$-th station.

If multiple trains are appointed to the same hour, their capacities are being added up and they are moving together.

The player wants to stay in the game for $$$t$$$ hours. Determine the minimum number of trains he will need for it.

Input format:
The first line contains three integers $$$n$$$, $$$t$$$, and $$$k$$$ ($$$1 \leq n, t \leq 200, 1 \leq k \leq 10^9$$$) — the number of stations on the line, hours we want to survive, and capacity of each train respectively.

Each of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ ($$$0 \leq a_i, b_i \leq c_i \leq 10^9$$$) — number of people at the $$$i$$$-th station in the beginning of the game, number of people arriving to $$$i$$$-th station in the end of each hour and maximum number of people at the $$$i$$$-th station allowed respectively.

Output format:
Output a single integer number — the answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's look at the sample. There are three stations, on the first, there are initially 2 people, 3 people on the second, and 4 people on the third. Maximal capacities of the stations are 10, 9, and 8 respectively.

One of the winning strategies is to appoint two trains to the first and the third hours. Then on the first hour, the train takes all of the people from the stations, and at the end of the hour, 4 people arrive at the first station, 3 on the second, and 2 on the third.

In the second hour there are no trains appointed, and at the end of it, the same amount of people are arriving again.

In the third hour, the train first takes 8 people from the first station, and when it arrives at the second station, it takes only 2 people because it can accommodate no more than 10 people. Then it passes by the third station because it is already full. After it, people arrive at the stations once more, and the game ends.

As there was no such moment when the number of people at a station exceeded maximal capacity, we won using two trains.

Example input:
3 3 10
2 4 10
3 3 9
4 2 8

Example output:
2

Example input:
4 10 5
1 1 1
1 0 1
0 5 8
2 7 100

Example output:
12

Editorial:
Let's enumerate the hours and the stations starting from zero. Let's add a station to the end with an infinite number of people and infinite capacity. It is obvious that it will not affect the answer. Also, every train now will be filled completely.
Let's calculate $$$sa[p]$$$, $$$sb[p]$$$ and $$$sc[p]$$$: the sum of $$$a[i]$$$, $$$b[i]$$$ and $$$c[i]$$$ over the first $$$p$$$ stations respectively.
Let $$$d[p][s][z]$$$ ($$$0 \leq p \leq n + 1$$$, $$$0 \leq s \leq t$$$, $$$0 \leq z \leq 1$$$) be the minimal number of trains (or $$$\infty$$$, if impossible) needed to hold on for $$$s$$$ hours, if there were only the first $$$p$$$ stations, so that every train we used would be filled completely. Herewith the initial number of people on the $$$i$$$-th station equals $$$z \cdot a[i]$$$.
Let $$$g[p][s][z]$$$ ($$$0 \leq p \leq n + 1$$$, $$$0 \leq s \leq t$$$, $$$0 \leq z \leq 1$$$)be the minimal number of trains (or $$$\infty$$$, if impossible) needed to hold on for $$$s$$$ with a half hours (so that we can send some trains at the end), if there were only the first $$$p$$$ stations, so that every train we used would be filled completely and every station except for the last would contain in the end $$$0$$$ people. Herewith the initial number of people on the $$$i$$$-th station equals $$$z \cdot a[i]$$$.
Then the answer for the problem is $$$d[n + 1][t][1]$$$.
Lets calculate $$$d$$$ and $$$g$$$ using dynamic programming.
In order to calculate $$$d[p][s][z]$$$ and $$$g[p][s][z]$$$ lets consider the last hour from $$$0$$$ to $$$s - 1$$$ in which some train will take a person from the last station. Notice that in case of $$$g[p][s][z]$$$ we do not consider the $$$s$$$-th hour though there could be such trains during this hour.
First case: There were no such trains. In this case we just need to check that the last station won't overflow and that $$$d[p - 1][s][z] \neq \infty$$$. Then we can make transitions: $$$$$$d[p][s][z] \leftarrow d[p - 1][s][z],$$$$$$ $$$$$$g[p][s][z] \leftarrow val = \left\lceil \frac{z \cdot sa[p - 1] + s \cdot sb[p - 1]}{k} \right\rceil.$$$$$$ The second transition is made only if $$$val \cdot k \leq z \cdot sa[p] + s \cdot sb[p]$$$.
(*) In case of $$$g[p][s][z]$$$ it is obvious that such number will be needed in order to set to zero all the stations except for the last one, and this number can be achieved since we can hold on for $$$s$$$ hours without taking a person from the last station.
Second case: denote the number of this hour by $$$r$$$. Then the plan is as follows:
1. First, we need to hold on for $$$r$$$ with a half hours and do so that on every station except for the last there will be $$$0$$$ people.
2. Then we possibly send some more trains during the $$$r$$$-th hour.
3. Then we need to hold on for $$$s - r$$$ without the first half hours without sending a train which will take a person from the last station.
4. Then in case of $$$g[p][s][z]$$$ we send some more trains during the $$$s$$$-th hour.
On the phase (2) we cat calculate the initial number of people on the last station: $$$m = z \cdot sa[p] + r \cdot sb[p] - k \cdot g[p][r][z]$$$, and then calculate the minimal number of trains we need to send so that the last station doesn't overflow by the end of the$$$(s-1)$$$-th hour: $$$x = \left\lceil \frac{\max(m + (s - r) \cdot b[p - 1] - c[p - 1], 0)}{k} \right\rceil$$$. If $$$x \cdot k > m$$$, then the transition is impossible, else it is benificial to send $$$x$$$ trains.
During the phase (3) it is beneficial to send as few trains as possible, be'cause in case of $$$d[p][s][z]$$$ it is the last phase, and in case of $$$g[p][s][z]$$$ we can always send additional trains during the phase (4) and nothing will change. Notice in the beginning of phase (3) the first $$$p - 1$$$ are empty and also we can assume we are starting from the beginning of an hour and we need to hold on for $$$s - r$$$ hours. Thus we need to send $$$d[p - 1][s - r][0]$$$ trains. If $$$d[p - 1][s - r][0] = \infty$$$, then the transition is impossible.
Finally, on the phase (4) we need to send as few trains as possible so that all the stations except for the last one would contain $$$0$$$ people. As in (*) we can see that on phases (3) and (4) we need to send in total at least val = $$$\left\lceil \frac{(s - r) \cdot sb[p - 1]}{k} \right\rceil$$$ trains, and we can achieve this number.
We can make transitions: $$$$$$d[p][s][z] \leftarrow g[p][r][z] + x + d[p - 1][s - r][0],$$$$$$ $$$$$$g[p][s][z] \leftarrow g[p][r][z] + x + \left\lceil \frac{(s - r) \cdot sb[p - 1]}{k} \right\rceil.$$$$$$ The second transition is made only if $$$val \cdot k \leq (s - r) \cdot sb[p]$$$.
Solution time is $$$O(n t^2)$$$.