제출 #827373

#제출 시각아이디문제언어결과실행 시간메모리
827373MadokaMagicaFanCloud Computing (CEOI18_clo)C++14
100 / 100
420 ms1424 KiB
#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;
}
#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...