Submission #1226333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226333		radodododo	Cloud Computing (CEOI18_clo)	C++20	100 / 100	646 ms	2176 KiB

clo

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

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10