제출 #1328448

#제출 시각아이디문제언어결과실행 시간메모리
1328448hamstpanCloud Computing (CEOI18_clo)C++20
100 / 100
1792 ms3732 KiB
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdint>
using namespace std;
struct obj {
	long long cnt, clock, val;
};
bool cmp(obj& a, obj& b) {
	if (a.clock == b.clock) return a.cnt < b.cnt; //process buying first
	return a.clock < b.clock;
}
const int MAXN = 200000;
long long dp1[200010], dp2[200010];
int main() {
	int n, m;
	cin >> n;
	vector<obj> comps;
	for (int i = 0; i < n; ++i) {
		int r, s, t;
		cin >> r >> s >> t;
		comps.push_back({ r, s, -t });
	}
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int r, s, t;
		cin >> r >> s >> t;
		comps.push_back({ -r, s, t });
	}
	sort(comps.rbegin(), comps.rend(), cmp);
	int k = comps.size();
	for (int j = 0; j <= MAXN; ++j) dp1[j] = -1e18;
	dp1[0] = 0;
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j <= MAXN; ++j) dp2[j] = dp1[j];
		for (int j = 0; j <= MAXN; ++j) {
			if (dp1[j] < (-1e17)) continue;
			if (j + comps[i].cnt >= 0 && j + comps[i].cnt <= MAXN) {
				dp2[j + comps[i].cnt] = max(dp2[j + comps[i].cnt], dp1[j] + comps[i].val);
				//cout << dp2[j + comps[i].cnt] << endl;
			}
		}
		for (int j = 0; j <= MAXN; ++j) {
			dp1[j] = dp2[j];
			dp2[j] = -1e18;
		}
		//long long ans = 0;
		//for (int i = 0; i <= MAXN; ++i) ans = max(ans, dp1[i]);
		//cout << ans << endl;
	}
	long long ans = 0;
	for (int i = 0; i <= MAXN; ++i) ans = max(ans, dp1[i]);
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...