TheProgrammingContestDivOne

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int64 INF = 1e16L;

class TheProgrammingContestDivOne {
  public:
    class problem {
      public:
        int64 m, d, t;

        bool operator < (const problem &A) const {
          return A.d * t <= d * A.t;
        }
    };

    int N, total_time;
    vector<problem> a;
    vector<vector<int64>> dp;

    void max_self(int64 &x, int64 y) {
      x = max(x, y);
    }

    int64 solve(int i, int t) {
      if (i == N)
        return 0LL;
      if (dp[i][t] != -INF)
        return dp[i][t];
      int64 best = solve(i + 1, t), new_time = t + a[i].t;
      if (new_time <= total_time) {
        int64 reward = a[i].m - a[i].d * new_time;
        if (reward >= 0) {
          int64 ans = solve(i + 1, new_time) + reward;
          max_self(best, ans);
        }
      }
      return dp[i][t] = best;
    }

    int find(int T, vector<int> maxPoints, vector<int> pointsPerMinute, vector<int> requiredTime) {
      N = maxPoints.size();
      total_time = T;
      for (int i = 0; i < N; ++i)
        a.push_back({maxPoints[i], pointsPerMinute[i], requiredTime[i]});
      sort(a.begin(), a.end());
      dp = vector<vector<int64>>(N, vector<int64>(total_time + 1, -INF));
      return solve(0, 0);
    }
};