Submission #60577499

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, k;
  cin >> n >> m >> k;
  vector<int> p(n), u(n), c(n);
  vector<vector<int>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i] >> u[i] >> c[i];
    c[i]--;
    a[c[i]].push_back(i);
  }

  vector<int64_t> f(m + 1, 0);
  for (int i = 0; i < n; i++) {
    if (a[i].empty()) continue;
    vector<int64_t> g(m + 1, -1e18);
    for (int t : a[i]) {
      for (int j = m; j >= p[t]; j--) {
        g[j] = max(g[j], g[j - p[t]] + u[t]);
      }
      for (int j = m; j >= p[t]; j--) {
        g[j] = max(g[j], f[j - p[t]] + u[t] + k);
      }
    }
    for (int j = 0; j <= m; j++) {
      f[j] = max(f[j], g[j]);
      if (j > 0) f[j] = max(f[j], f[j - 1]);
    }
  }
  cout << f[m] << '\n';

  return 0;
}

Submission Info

Judge Result