Submission #826626

#	Time	Username	Problem	Language	Result	Execution time	Memory
826626		georgievskiy	Cloud Computing (CEOI18_clo)	C++17	100 / 100	965 ms	3612 KiB

clo

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

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

const int N = 2004, K = 101;
const ll inf = 1e15;
ll dp[2][N][K];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	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());
	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 = 1; i <= n; i++) {
		int i2 = i & 1;
		auto& comp = a[i - 1];

		// j == 0
		for (int k = 0; k < K; k++) {
			auto& v = dp[i2][0][k];
			max_(v, dp[1 - i2][0][k]);
			if (k - comp.c >= 0)
				max_(v, dp[1 - i2][0][k - comp.c] - comp.v);
		}

		for (int j = 1; j <= m; j++) {
			auto& cust = q[j - 1];

			for (int k = comp.c; k < K; k++) {
				auto& v = dp[i2][j][k];
				max_(v, dp[1 - i2][j][k - comp.c] - comp.v);
			}
			if (comp.f >= cust.f) {
				for (int k = 0; k < K - cust.c; k++) {
					auto& v = dp[i2][j][k];
					max_(v, dp[i2][j - 1][k + cust.c] + cust.v);
				}
			}

			for (int k = 0; k < K; k++) {
				auto& v = dp[i2][j][k];
				max_(v, max(dp[1 - i2][j][k], dp[i2][j - 1][k]));
				// if (k - comp.c >= 0)
				// 	max_(v, dp[1 - i2][j][k - comp.c] - comp.v);
				// if (k + cust.c < K && comp.f >= cust.f)
				// 	max_(v, dp[i2][j - 1][k + cust.c] + cust.v);
				max_(ans, v);
			}
			// for (int k = 0; k < K; k++)
			// 	cout << i << " " << j << " " << k << " " << dp[i2][j][k] << "\n";
		}
	}
	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