Submission #906411

#	Time	Username	Problem	Language	Result	Execution time	Memory
906411		Nonoze	Cloud Computing (CEOI18_clo)	C++17	100 / 100	670 ms	2384 KiB

clo

#include <bits/stdc++.h>

#define int long long
#define sz(x) (int)(x.size())

using namespace std;

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

int n, m;
vector<computer> a;

void solve() {
	cin >> n;
	a.clear();
	a.resize(n);
	for (auto &u: a) {
		cin >> u.c >> u.f >> u.v;
		u.v*=-1;
	}
	cin >> m;
	for (int i=0; i<m; i++) {
		int c, f, v; cin >> c >> f >> v;
		c*=-1;
		a.push_back({c, f, v});
	}
	sort(a.begin(), a.end());
	vector<int> dp(50*n+10, -1e15);
	vector<int> lst(50*n+10, -1e15);
	lst[0]=0;
	dp[0]=0;
	for (int tt=0; tt<n+m; tt++) {
		for (int i=0; i<=50*n; i++) {
			if (i+a[tt].c>50*n || i+a[tt].c<0) continue;
			dp[i+a[tt].c]=max(lst[i+a[tt].c], lst[i]+a[tt].v);
		}
		lst=dp;
	}
	cout << *max_element(dp.begin(), dp.end()) << endl;
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	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