I recently started learning Dynamic Programming, and am currently trying to solve “Roller Coaster Fun” on Kattis. However, I’m only getting 10/30 test cases, and am stuck on what I am doing wrong.

My thinking is very similar to the coin problem (7.1 in the CPH, scroll down to “Coin Problem”), where we find the answer for each of the 25,000 times using the previous ones:

(this is pseudocode)

```
// fun[i] is the maximum amount of fun possible at time i
// k[i][j] is the number of times Jimmy goes on coaster j at time i
// all other functions/variables are as given in the problem
fun[1] = 0
fun[n] = max(fun[n - 1], // last fun value (don't go on any new ride)
fun[n - t[0]] + f(0, k[n][0]),
...,
fun[n - t[i]] + f(i, k[n][i]),
...,
fun[n - t[N - 1]] + f(N - 1, k[n][N - 1]))
```

Here is my full code:

```
// https://open.kattis.com/problems/rollercoasterfun
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100
#define MAX_T 25000
vector<int> a(MAX_N), b(MAX_N), t(MAX_N);
vector<int> dp(MAX_T + 1);
vector<vector<int>> k(MAX_T + 1, vector<int>(MAX_N));
int f(int time, int i)
{
return max(0, a[i] - k[time][i] * k[time][i] * b[i]);
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; ++i)
cin >> a[i] >> b[i] >> t[i];
dp[0] = 0;
fill(k[0].begin(), k[0].end(), 0);
for (int time = 1; time <= MAX_T; ++time)
{
dp[time] = dp[time - 1];
k[time] = k[time - 1];
for (int i = 0; i < N; ++i)
{
if (time - t[i] >= 0)
{
int newFun = dp[time - t[i]] + f(time - t[i], i);
if (newFun > dp[time])
{
dp[time] = newFun;
k[time] = k[time - t[i]];
++k[time][i]; // go on this ride one more time
}
}
}
// cout << time << ' ' << dp[time] << '\n';
}
int Q;
cin >> Q;
int q;
for (int i = 0; i < Q; ++i)
{
cin >> q;
cout << dp[q] << '\n';
}
return 0;
}
```

Any help would be appreciated!