제출 #678378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678378		42kangaroo	Cloud Computing (CEOI18_clo)	C++17	100 / 100	422 ms	1364 KiB

clo

//
// Created by 42kangaroo on 05/01/2023.
//
#include "bits/stdc++.h"

using namespace std;

#define int long long

struct Comp {
	int c, r, p;
	bool order;
};

bool operator<(const Comp& l, const Comp& r) {
	return tie(r.r, l.order) < tie(l.r, r.order);
}

signed main() {
	int n;
	cin >> n;
	vector<Comp> cp(n);
	int s = 0;
	for (auto& c:cp) {
		cin>> c.c >> c.r >> c.p;
		s += c.c;
		c.order = false;
	}
	int m;
	cin >> m;
	cp.resize(n + m);
	for (int i = n; i < n + m; ++i) {
		cin >> cp[i].c >> cp[i].r >> cp[i].p;
		cp[i].order = true;
	}
	std::sort(cp.begin(), cp.end());
	vector<int> dp(s + 1, numeric_limits<int>::min());
	dp[0] = 0;
	for (auto& o: cp) {
		if (o.order) {
			for (int i = 0; i <= s - o.c; ++i) {
				if (dp[i+o.c] != numeric_limits<int>::min()) {
					dp[i] = max(dp[i], dp[i + o.c] + o.p);
				}
			}
		} else {
			for (int i = s; i >= o.c; --i) {
				if (dp[i - o.c] != numeric_limits<int>::min()) {
					dp[i] = max(dp[i], dp[i - o.c] - o.p);
				}
			}
		}
	}
	int ma = numeric_limits<int>::min();
	for (int i = 0; i <= s; ++i) {
		ma = max(ma, dp[i]);
	}
	cout << ma << "\n";
}/*
4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550*/

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