Submission #1011212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011212		ef10	Cloud Computing (CEOI18_clo)	C++17	100 / 100	644 ms	2392 KiB

clo

// Source: https://usaco.guide/general/io

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

#define LL long long

LL N, M;
tuple<LL,LL,LL> A[4005];

int main() {
	cin >> N;
	LL maxc = 0;
	for (LL i = 1; i <= N; i++) {
		LL a,b,c; cin >> a >> b >> c;
		A[i] = make_tuple(a,b,-c);
		maxc += a;
	}
	cin >> M;
	for (LL i = N+1; i <= N+M; i++) {
		LL a,b,c; cin >> a >> b >> c;
		A[i] = make_tuple(-a,b,c);
	}
	sort(A+1, A+N+M+1, [](const tuple<LL,LL,LL>& a, const tuple<LL,LL,LL>& b) {
		return (get<1>(a) > get<1>(b)) || (get<1>(a) == get<1>(b) && get<0>(a) > get<0>(b));
	});
	//for (LL i = 1; i <= A)
	LL dp[2][maxc+1]; memset(dp,0,sizeof(dp));
	bool bp[2][maxc+1]; memset(bp,0,sizeof(bp));
	LL ind;
	for (LL i = 1; i <= N+M; i++) {
		ind = i % 2;
		LL oi = (i+1) % 2;
		if (get<0>(A[i]) > 0) {
			if (bp[ind][get<0>(A[i])]) {
				dp[ind][get<0>(A[i])] = max(dp[ind][get<0>(A[i])], get<2>(A[i]));
			} else {
				dp[ind][get<0>(A[i])] = get<2>(A[i]);
				bp[ind][get<0>(A[i])] = true;
			}
		}
		for (LL j = 0; j <= maxc; j++) {
			if (bp[oi][j]) {
				if (bp[ind][j]) {
					dp[ind][j] = max(dp[ind][j], dp[oi][j]);
				} else {
					bp[ind][j] = true;
					dp[ind][j] = dp[oi][j];
				}
			}
			if (bp[oi][j] && j + get<0>(A[i]) >= 0) {
				if (bp[ind][j + get<0>(A[i])]) {
					dp[ind][j + get<0>(A[i])] = max(dp[ind][j + get<0>(A[i])], dp[oi][j] + get<2>(A[i]));
				} else {
					bp[ind][j + get<0>(A[i])] = true;
					dp[ind][j + get<0>(A[i])] = dp[oi][j] + get<2>(A[i]);
				}
			}
		}
		memset(dp[oi],0,sizeof(dp[oi]));
		memset(bp[oi],0,sizeof(bp[oi]));
	}
	LL res = 0;
	for (LL i = 0; i <= maxc; i++) {
		if (bp[ind][i]) {
			res = max(res,dp[ind][i]);
		}
	}
	cout << res << endl;
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:30:5: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |  LL ind;
      |     ^~~

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