Submission #706456

#	Time	Username	Problem	Language	Result	Execution time	Memory
706456		LucasLe	Cloud Computing (CEOI18_clo)	C++17	100 / 100	816 ms	2004 KiB

clo

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct pro {
	int cores;
	int fan;
	int price;
} comp[4001];

int main() {

	int N; cin >> N;
	int maxc = 0;
	for (int i = 0; i < N; ++i) {
		cin >> comp[i].cores >> comp[i].fan >> comp[i].price;
		comp[i].price = -comp[i].price;
		maxc += comp[i].cores;
	}

	int M; cin >> M;

	for (int i = N; i < N + M; ++i) {
		cin >> comp[i].cores >> comp[i].fan >> comp[i].price;
		comp[i].cores = -comp[i].cores;
	}

	sort(comp, comp + N + M,[](const pro &A, const pro &B){
		return (A.fan != B.fan) ? A.fan > B.fan : A.price < B.price; 
	});

	vector<ll> pref(maxc + 1, INT64_MIN), now(maxc + 1, INT64_MIN);
	pref[0] = 0; now[0] = 0;
	for (int i = 0; i < N + M; ++i) {
		for (int c = 0; c <= maxc; ++c) {
			int pref_cores = c - comp[i].cores;
			if (0 <= pref_cores && pref_cores <= maxc && pref[pref_cores] != INT64_MIN) {
				now[c] = max(now[c], pref[pref_cores] + comp[i].price);
			}
		}
		for (int c = 0; c <= maxc; ++c) pref[c] = now[c];
		//cout << now[0] << '\n';
	}
	
	cout << *max_element(pref.begin(), pref.end());
}

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