Submission #754299

#	Time	Username	Problem	Language	Result	Execution time	Memory
754299		MetalPower	Cloud Computing (CEOI18_clo)	C++14	100 / 100	492 ms	2064 KiB

clo

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

#define ll long long
#define pii pair<int, int>
#define pli pair<int, pii>
#define fi first
#define se second

const int MN = 1e5 + 10;
const ll INF = 1e18;

int N, M;
ll dp[2][MN];
vector<pli> vec;

void chmax(ll& a, ll b){
	if(b > a) a = b;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for(int i = 0; i < N; i++){
		int c, f, v; cin >> c >> f >> v;
		vec.push_back({f, {c, -v}});
	}

	cin >> M;
	for(int i = 0; i < M; i++){
		int c, f, v; cin >> c >> f >> v;
		vec.push_back({f, {-c, v}});
	}

	int sz = vec.size();
	sort(vec.begin(), vec.end(), greater<pli>());

	dp[0][0] = 0;
	for(int j = 1; j < MN; j++) dp[0][j] = -INF;

	int id = 1;
	for(int i = 0; i < sz; i++){
		for(int j = 0; j < MN; j++){
			dp[id][j] = dp[id ^ 1][j];
			int pre = j - vec[i].se.fi;
			if(MN > pre && pre >= 0) chmax(dp[id][j], dp[id ^ 1][pre] + vec[i].se.se);
		}
		id ^= 1;
	}

	ll ans = 0;
	for(int j = 0; j < MN; j++) chmax(ans, dp[id ^ 1][j]);
	cout << ans << '\n';
}

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