Submission #24973879

---

Source Code Expand

#include "bits/stdc++.h"

#define int long long

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = (1LL << 61);
ll mod = 1000000007;

int dp[5020][5020];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N; cin >> N;
	vector<pair<int, P>>p;
	for (int i = 0; i < N; i++) {
		int D, C, S; cin >> D >> C >> S;
		p.push_back({ D, {C, S} });
	}
	sort(p.begin(), p.end());
	for (int j = 0; j <= 5010; j++) {
		for (int i = 0; i < N; i++) {
			if (j + p[i].second.first <= p[i].first) {
				dp[i + 1][j + p[i].second.first] = max(dp[i + 1][j + p[i].second.first], dp[i][j] + p[i].second.second);
			}
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);

		}
	}
	int ans = 0;
	for (int i = 0; i < 5010; i++) {
		ans = max(ans, dp[N][i]);
	}
	cout << ans << endl;
	return 0;


}

Submission Info

Judge Result