Submission #166186

#	Time	Username	Problem	Language	Result	Execution time	Memory
166186		Eae02	Cloud Computing (CEOI18_clo)	C++17	100 / 100	568 ms	2300 KiB

clo

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using ll = long long;
using namespace std;

struct Item {
	ll c, f, p;
	bool operator<(const Item& o) const {
		return make_tuple(-f, -c) < make_tuple(-o.f, -o.c);
	}
};

vector<Item> items;

int main() {
	ll n; cin >> n;
	for (ll i = 0; i < n; i++) {
		Item& item = items.emplace_back();
		cin >> item.c >> item.f >> item.p;
		item.p = -item.p;
	}
	
	ll m; cin >> m;
	for (ll i = 0; i < m; i++) {
		Item& item = items.emplace_back();
		cin >> item.c >> item.f >> item.p;
		item.c = -item.c;
	}
	
	sort(all(items));
	
	constexpr ll MAX_C = 2000 * 50 + 10;
	vector<ll> dpPrev(MAX_C);
	vector<ll> dpNext(MAX_C);
	
	for (ll i = items.size() - 1; i >= 0; i--) {
		for (ll c = 0; c < -items[i].c; c++) {
			dpNext[c] = dpPrev[c];
		}
		for (ll c = max(-items[i].c, 0LL); c < MAX_C; c++) {
			dpNext[c] = max(dpPrev[c], dpPrev[c + items[i].c] + items[i].p);
		}
		dpNext.swap(dpPrev);
	}
	
	cout << dpPrev[0] << "\n";
}

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