제출 #1180353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180353		prism7k	Cloud Computing (CEOI18_clo)	C++17	100 / 100	289 ms	1452 KiB

clo

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXC = 60 * 2000;
ll dp[MAXC + 1];

const ll inf = 1e16;

int main() {
	
	fill(dp, dp + MAXC + 1, -inf);
	vector<tuple<int, int, int>> purchases;
	int n; cin >> n;
	
	int c, f, v;
	for(int i = 0; i < n; ++i) {
		cin >> c >> f >> v;
		purchases.push_back({c, f, -v});
	}
	
	int m; cin >> m;
	for(int i = 0; i < m; ++i) {
		cin >> c >> f >> v;
		purchases.push_back({-c, f, v});
	}
	
	sort(purchases.begin(), purchases.end(), [](
		const tuple<int, int, int> &p1, const tuple<int, int, int> &p2) {
		int f_1 = get<1>(p1);
		int f_2 = get<1>(p2);
		int c_1 = get<0>(p1);
		int c_2 = get<0>(p2);
		if(f_1 != f_2) return f_1 > f_2;
		else return c_1 > c_2;
	});
	
	dp[0] = 0;
	ll mx = -inf;
	for(auto[cc, ff, vv] : purchases) {
		//cout << cc << " " << ff << " " << vv << "\n";
		if(cc >= 0) {
			for(int i = MAXC; i >= cc; --i) {
				if(dp[i - cc] != -inf) {
					dp[i] = max(dp[i], dp[i - cc] + vv);
				}
			}
		} else {
			for(int i = 0; i - cc <= MAXC; ++i) {
				if(dp[i - cc] != -inf) {
					dp[i] = max(dp[i], dp[i - cc] + vv);
				}
			}
		}

	}
	
	for(int i = 0; i <= MAXC; ++i) mx = max(dp[i], mx);
	cout << mx << "\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