Submission #487097

#	Time	Username	Problem	Language	Result	Execution time	Memory
487097		nicolexxuu	Cloud Computing (CEOI18_clo)	C++14	72 / 100	812 ms	1988 KiB

clo

#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct Transaction {
	int c, f, v;
	bool operator <(const Transaction& other) { return f > other.f; }
};

ll dp[2][100001];
int main() {
	vector<Transaction> trans;
	int n; cin >> n;
	for(int i = 0; i < n; i++) {
		trans.push_back(Transaction());
		int c, f, v;
		cin >> c >> f >> v;
		trans[i].c = c;
		trans[i].f = f;
		trans[i].v = -v;
	}
	
	int m; cin >> m;
	for(int i = 0; i < m; i++) {
		trans.push_back(Transaction());
		int C, F, V;
		cin >> C >> F >> V;
		trans[n+i].c = -C;
		trans[n+i].f = F;
		trans[n+i].v = V;
	}
	
	sort(trans.begin(), trans.end());
	
	for(int j = 0; j <= 100000; j++) dp[0][j] = LLONG_MIN;
	dp[0][0] = 0;
	
	for(int t = 0; t < n+m; t++) {
		Transaction tn = trans[t];
		copy(begin(dp[0]), end(dp[0]), begin(dp[1]));
		for(int c = 100000; c >= max(tn.c, 0); c--) {
			if(c-tn.c <= 100000 && dp[0][c-tn.c] != LLONG_MIN)
					dp[1][c] = max(dp[1][c], dp[0][c-tn.c] + tn.v);
//			if(dp[1][c] != INT_MIN) {
//				cout << "t: " << t << " c : " << c << endl;
//				cout << "c-tnc: " << dp[1][c-tn.c] << " v: " << tn.v << endl;
//				cout << "dp: " << dp[1][c] << endl;
//			}
		}
		swap(dp[0], dp[1]);
	}
	
	ll res = 0;
	for(ll l : dp[0]) res = max(res, l);
	cout << res << endl;
}

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