Submission #906489

#	Time	Username	Problem	Language	Result	Execution time	Memory
906489		belgianbot	Cloud Computing (CEOI18_clo)	C++14	100 / 100	653 ms	2388 KiB

clo

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct a{
	int c, f, v;
	
	bool operator< (const a &b) const {
		if (f == b.f) {
			return (c > b.c);
		}
		return (f > b.f);
	}
	bool operator> (const a &b) const {
		if (f == b.f) {
			return (c < b.c);
		}
		return (f < b.f);
	}
};

int N, M;

vector<a> vec;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	
	for (int i(0); i < N; i++) {
		a l; cin >> l.c >> l.f >> l.v;
		l.v *= -1;
		vec.push_back(l);
	}
	
	cin >> M;
	for (int i(0); i < M; i++) {
		a l; cin >> l.c >> l.f >> l.v;
		l.c *= -1;
		vec.push_back(l);
	}
	
	sort(vec.begin(), vec.end());
	
	vector <int> dp(N * 50 + 10, -1e15), saved(N * 50 + 10, -1e15);
	dp[0] = 0;
	saved[0] = 0;
	for (int i(0); i < N + M; i++) {
		for (int j(0); j < 50 * N + 1; j++) {
			if (j + vec[i].c < 0 || j + vec[i].c > 50 * N) continue;
			saved[j + vec[i].c] = max(dp[j + vec[i].c], dp[j] + vec[i].v);
		}
		dp = saved;
		
	}
	cout << *max_element(dp.begin(), dp.end()) << '\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