Submission #934416

#TimeUsernameProblemLanguageResultExecution timeMemory
934416garamlee500Cloud Computing (CEOI18_clo)C++17
36 / 100
299 ms2384 KiB
#include <iostream>
#include <algorithm>


using namespace std;

struct item {
	int cores;
	int clock;
	long long money;
	bool isComputer;
	item(int cores, int clock, long long money, bool isComputer) :
		cores(cores),
		clock(clock),
		money(money),
		isComputer(isComputer)	
	{

	}

	item() = default;
};

item items[4000];
long long dp[100001];


int n, m, c, f, nm;
long long v;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> c >> f >> v;
		items[i] = item(c, f, v, true);
	}
	cin >> m;
	nm = n + m;
	for (int i = n; i < nm; i++) {
		cin >> c >> f >> v;
		items[i] = item(c, f, v, false);
	}
	// put to left those with larger clock speeds,
	// prefering computers first.
	sort(begin(items), begin(items) + nm,

		[](item& a, item& b) {
			if (a.clock == b.clock) {
				return a.isComputer;
			}

			return a.clock > b.clock;
		});

	for (int i = 1; i <= 100000; i++) {
		dp[i] = -10000000000000000;
	}
	dp[0] = 0;
	for (int i = 0; i < nm; i++) {
		item item1 = items[i];
		if (item1.isComputer) {
			for (int newCoreCount = 100000; newCoreCount >= item1.cores; newCoreCount--) {
				dp[newCoreCount] = max(dp[newCoreCount], dp[newCoreCount - item1.cores] - item1.money);
			}
		}
		else {
			for (int newCoreCount = 0; newCoreCount + item1.cores <= 100000; newCoreCount++) {
				dp[newCoreCount] = max(dp[newCoreCount], dp[newCoreCount + item1.cores] + item1.money);
			}
		}
	}
	long long best = 0;
	for (int i = 0; i <= 100000; i++) {
		best = max(best, dp[i]);
	}
	cout << best << '\n';

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