Submission #1217159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217159		Tob	Cloud Computing (CEOI18_clo)	C++20	100 / 100	462 ms	2256 KiB

clo

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 4007, C = 1e5 + 7;
const ll inf = 1e18;

int n, m;
int a[N], b[N], c[N];
ll dp[2][C];

int main () {
	FIO;
	cin >> n;
	
	vector <pii> v;
	for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i], v.pb({b[i], -i});
	cin >> m;
	for (int i = n; i < n+m; i++) cin >> a[i] >> b[i] >> c[i], v.pb({b[i], -i});
	sort(all(v));
	reverse(all(v));
	
	for (int i = 1; i < C; i++) dp[0][i] = -inf;
	
	for (int i = 0, o = 1; i < n+m; i++, o ^= 1) {
		int x = -v[i].S;
		if (x < n) {
			for (int j = 0; j < C; j++) dp[o][j] = dp[o^1][j];
			for (int j = 0; j+a[x] < C; j++) if (dp[o^1][j]-c[x] > dp[o][j+a[x]]) dp[o][j+a[x]] = dp[o^1][j]-c[x];
		}
		else {
			for (int j = 0; j < C; j++) dp[o][j] = dp[o^1][j];
			for (int j = a[x]; j < C; j++) if (dp[o^1][j]+c[x] > dp[o][j-a[x]]) dp[o][j-a[x]] = dp[o^1][j]+c[x];
		}
	}
	ll mx = 0;
	for (int i = 0; i < C; i++) mx = max(mx, dp[(n+m)%2][i]);
	cout << mx;

	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