제출 #906465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906465		belgianbot	Cloud Computing (CEOI18_clo)	C++14	72 / 100	3039 ms	5552 KiB

clo

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

using namespace std;

struct a{
	int c, f, v;
	
	bool operator< (const a &b) const {
		if (f == b.f) {
			return (c > b.c);
		}
		return (f > b.f);
	}
	bool operator> (const a &b) const {
		if (f == b.f) {
			return (c < b.c);
		}
		return (f < b.f);
	}
};

int N, M;

vector<a> vec;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	
	for (int i(0); i < N; i++) {
		a l; cin >> l.c >> l.f >> l.v;
		l.v *= -1;
		vec.push_back(l);
	}
	
	cin >> M;
	for (int i(0); i < M; i++) {
		a l; cin >> l.c >> l.f >> l.v;
		l.c *= -1;
		vec.push_back(l);
	}
	
	sort(vec.begin(), vec.end());
	
	vector <int> dp(N * 50 + 1, INT_MIN);
	vector<bool> processed(N * 50 + 1, false);
	processed[0] = true;
	dp[0] = 0;
	int ans(0), biggest(0);
	for (int i(0); i < N + M; i++) {
		vector<pair<int,int>>changed;
		for (int j(biggest); j >= 0; j--) {
			if (!processed[j]) continue;
			if (j + vec[i].c < 0) continue;
			if (!processed[j + vec[i].c]) {
				changed.push_back({j + vec[i].c, dp[j] + vec[i].v});
			}
			else {
				if (dp[j + vec[i].c] < dp[j] + vec[i].v) changed.push_back({j + vec[i].c, dp[j] + vec[i].v});
			}
		}
		for (auto j : changed) {
			ans = max(ans, j.second);
			dp[j.first] = j.second;
			processed[j.first] = true;
			biggest = max(biggest, j.first);
		}
		
	}
	cout << ans << '\n';
	return 0;
}

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