Submission #826608

#	Time	Username	Problem	Language	Result	Execution time	Memory
826608		georgievskiy	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1620 ms	3616 KiB

clo

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

#define max_(a, b) a = max((a), (b))
#define ll long long

const int N = 2004, K = 102;
ll dp[2][N][K];

int main() {
	int n;
	cin >> n;
	struct st {
		int c, f, v;
		bool operator<(st ot) {
			return f < ot.f;
		}
	};
	vector<st> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i].c >> a[i].f >> a[i].v;
	int m;
	cin >> m;
	vector<st> q(m);
	for (int i = 0; i < m; i++)
		cin >> q[i].c >> q[i].f >> q[i].v;
	sort(a.rbegin(), a.rend()), sort(q.rbegin(), q.rend());
	ll int inf = 1e12;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j <= m; j++)
			for (int k = 0; k < K; k++) dp[i][j][k] = -inf;

	dp[0][0][0] = 0;

	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		int i2 = i & 1;
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k < K; k++) {
				auto& v = dp[i2][j][k];
				auto comp = i ? a[i - 1] : st{0, 0, 0}, cust = j ? q[j - 1] : st{0, 0, 0};

				if (i)
					max_(v, dp[1 - i2][j][k]);
				if (j)
					max_(v, dp[i2][j - 1][k]);
				if (i && k - comp.c >= 0)
					max_(v, dp[1 - i2][j][k - comp.c] - comp.v);
				if (j && k + cust.c < K && comp.f >= cust.f)
					max_(v, dp[i2][j - 1][k + cust.c] + cust.v);
				// cout << i << " " << j << " " << k << " " << v << "\n";
				max_(ans, v);
				if (v <= -(inf / 10))
					v = -inf;
			}
			// max_(ans, dp[i2][j][0]);
		}
	}
	cout << ans << "\n";

	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