Submission #827373

#	Time	Username	Problem	Language	Result	Execution time	Memory
827373		MadokaMagicaFan	Cloud Computing (CEOI18_clo)	C++14	100 / 100	420 ms	1424 KiB

clo

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define pb push_back

const ll inf = 1e16;

int main() {
	int n, m, w;
	ll a, c, d;
	ll ans = 0;
	cin >> n;
	vector<ll> dp(n*50+100, -inf);
	vector<array<ll, 4>> q;
	dp[0] = 0;
	w = n*50+1;

	for (int i = 0; i < n; ++i) {
		cin >> c >> a >> d;
		q.pb({a, 1ll, c, -d});
	}

	cin >> m;
	for (int i = 0; i < m; ++i) {
		cin >> c >> a >> d;
		q.pb({a, 0ll, c, d});
	}

	sort(q.rbegin(), q.rend());

	for (auto u : q) {
		if (u[1]) {
			for (int i = w-1; i >= u[2]; --i)
				dp[i] = max(dp[i], dp[i-u[2]] + u[3]);
		} else {
			for (int i = 0; i < w; ++i)
				dp[i] = max(dp[i], dp[i+u[2]] + u[3]);
		}
	}

	for (auto x : dp)
		ans = max(ans, x);
	cout << ans << endl;
}

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