Submission #761548

#	Time	Username	Problem	Language	Result	Execution time	Memory
761548		penguinhacker	Cloud Computing (CEOI18_clo)	C++17	100 / 100	219 ms	1308 KiB

clo

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

#define ll long long
#define ar array

const int mxN=2000;
int n, m;
ll dp[50*mxN+1];
vector<ar<int, 4>> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i) {
		int c, f, p;
		cin >> c >> f >> p;
		v.push_back({-f, 1, c, p});
	}
	cin >> m;
	for (int i=0; i<m; ++i) {
		int c, f, p;
		cin >> c >> f >> p;
		v.push_back({-f, 2, c, p});
	}
	sort(v.begin(), v.end());
	memset(dp, 0xbf, sizeof(dp));
	dp[0]=0;
	int tot=0;
	for (auto [aalala, t, c, p] : v) {
		if (t==1) {
			tot+=c;
			for (int i=tot; i>=c; --i)
				dp[i]=max(dp[i], dp[i-c]-p);
		} else {
			for (int i=0; i<=tot-c; ++i)
				dp[i]=max(dp[i], dp[i+c]+p);
		}
		/*for (int i=0; i<=tot; ++i)
			cout << (dp[i]<1e18?-10000000:dp[i]) << " " << " ";
		cout << endl;*/
	}
	cout << *max_element(dp, dp+50*n+1);
	return 0;
}

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