SRM 502 Div1 Medium

main.cpp

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 60;
const int MAXT = 1e5 + 10;

class TheProgrammingContestDivOne {
  using ll = long long;

  ll dp[MAXT];

  struct Helper {
    int m;
    int r;
    int p;

    Helper(int _m, int _r, int _p) : m(_m), r(_r), p(_p) {}

    bool operator<(const Helper& h) const {
      return 1LL * r * h.p < 1LL * h.r * p;
    }
  };

 public:
  TheProgrammingContestDivOne() { memset(dp, 0, sizeof dp); }

  int find(int T, vector<int> maxPoints, vector<int> pointsPerMinute,
           vector<int> requiredTime) {
    vector<Helper> v;
    size_t size = maxPoints.size();

    for (auto i = 0; i < size; i++) {
      v.emplace_back(maxPoints[i], requiredTime[i], pointsPerMinute[i]);
    }

    sort(v.begin(), v.end());

    ll ans = 0;

    for (int i = 0; i < size; i++) {
      for (int j = T; j >= v[i].r; j--) {
        ll score = 1LL * v[i].m - 1LL * j * v[i].p;
        if (score < 0) {
          score = 0;
        }
        dp[j] = max(dp[j], dp[j - v[i].r] + score);
        ans = max(ans, dp[j]);
      }
    }

    return ans;
  }
};

int main() {
  cout << TheProgrammingContestDivOne().find(40000, {100000, 100000},
                                             {1, 100000}, {50000, 30000})
       << endl;
}