제출 #1226324

#제출 시각아이디문제언어결과실행 시간메모리
1226324radodododoCloud Computing (CEOI18_clo)C++20
54 / 100
115 ms157352 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node {
	long long c, f, w, tip;
	node(long long c = 0, long long f = 0, long long w = 0, long long tip = 0) {
		this->c = c;
		this->f = f;
		this->w = w;
		this->tip = tip;
	}
};

bool cmp(node a, node b) {
	return (a.f < b.f) || (a.f == b.f && a.tip < b.tip);
}

int main() {
	long long n;
	cin >> n;
	vector<node> v(n);
	for (long long i = 0; i < n; i++) {
		cin >> v[i].c >> v[i].f >> v[i].w;
		v[i].tip = 1;
	}
	long long m;
	cin >> m;
	for (long long i = 0; i < m; i++) {
		long long c, f, w;
		cin >> c >> f >> w;
		v.push_back(node(c, f, w, 0));
	}
	long long siz = 5000 + 1;
	long long inf = 1e18;
	sort(v.begin(), v.end(), cmp);
	reverse(v.begin(), v.end());
	vector<vector<long long>> dp(v.size() + 1, vector<long long>(siz, -inf));
	dp[0][0] = 0;
	long long ans = 0;
	for (long long i = 0; i < v.size(); i++) {
		dp[i + 1] = dp[i];
		for (long long x = 0; x < siz; x++) {
			if (v[i].tip == 1 && dp[i][max(x - v[i].c, (long long)0)] != -inf) {
				dp[i + 1][x] = max(dp[i][x], dp[i][max(x - v[i].c, (long long)0)] - v[i].w);
			}
			if (v[i].tip == 0 && x + v[i].c < siz && dp[i][x + v[i].c] != -inf) {
				dp[i + 1][x] = max(dp[i][x], dp[i][x + v[i].c] + v[i].w);
			}
			ans = max(ans, dp[i + 1][x]);
		}
	}
	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...