Submission #966238

#TimeUsernameProblemLanguageResultExecution timeMemory
966238vjudge1Cloud Computing (CEOI18_clo)C++17
100 / 100
558 ms2140 KiB
#include <bits/stdc++.h>
using namespace std;

int32_t main() { 
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int32_t n; cin >> n;
	enum { BUY, SELL };
	vector<tuple<int32_t, bool, int32_t, int32_t>> a;

	for (int32_t i = 0; i < n; i++) {
		int32_t c, f, v; cin >> c >> f >> v;
		a.emplace_back(-f, BUY, c, v);
	}

	int32_t m; cin >> m;
	for (int32_t i = 0; i < m; i++) {
		int32_t c, f, v; cin >> c >> f >> v;
		a.emplace_back(-f, SELL, c, v);
	}

	sort(a.begin(), a.end());
	constexpr int32_t MAX_CORES = 100'000;
	constexpr int64_t INF = 1e15;
	

	vector<int64_t> dp(MAX_CORES + 1, -INF);
	dp[0] = 0;

	for (auto [f, type, c, v] : a) {
		auto nxt = dp;
		for (int32_t cores = 0; cores <= MAX_CORES; cores++) {
			if (type == BUY && cores >= c) {
				nxt[cores] = max(dp[cores], dp[cores - c] - v);
			} else if (type == SELL && cores + c <= MAX_CORES) {
				nxt[cores] = max(dp[cores], dp[cores + c] + v);
			}
		}
		swap(nxt, dp);
	}

	cout << *max_element(dp.begin(), dp.end()) << '\n';

	return 0;

}
#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...