제출 #541918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541918		nafis_shifat	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1663 ms	2008 KiB

clo

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const ll inf=1e18;
int n, m;
int c[mxn];
ll f[mxn], v[mxn];
int main() {
	cin >> n;

	int tot = 0;

	for(int i = 1; i <= n; i++) {
		cin >> c[i] >> f[i] >> v[i];
		tot += c[i];
	}

	int m;
	cin >> m;

	for(int i = n + 1; i <= n + m; i++) {
		cin >> c[i] >> f[i] >> v[i];
	}

	vector<int> ord(n + m);
	iota(ord.begin(), ord.end(), 1);
	sort(ord.begin(), ord.end(), [](int a, int b) {
		if(f[a] == f[b]) return a < b;
		return f[a] > f[b];
	});

	ll dp[tot + 55] = {};
	ll cur[tot + 55] = {};

	for(int j = 0; j < tot + 55; j++) dp[j] = cur[j] = -inf;
	dp[0] = 0;
    ll ans = 0;
    int cc = 0;
	for(int i = 1; i <= n + m; i++) {

		int x = ord[i - 1];
		if(x <= n) cc += c[x];
		for(int j = 0; j <= cc; j++) cur[j] = -inf;




		for(int j = 0;j <= cc; j++) {
			if(x <= n) {
				cur[j] = dp[j];
				if(j >= c[x]) cur[j] = max(cur[j], dp[j - c[x]] - v[x]);
			} else {
				cur[j] = max(dp[j], dp[j + c[x]] + v[x]);
			}
			ans = max(ans, cur[j]);

		}

		for(int j = cc; j >= 0; j--) cur[j] = max(cur[j], cur[j + 1]);
		for(int j = 0; j <= cc; j++) dp[j] = cur[j];
	}

	cout<<ans<<endl;
}

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