Submission #810585

#	Time	Username	Problem	Language	Result	Execution time	Memory
810585		welleyth	Cloud Computing (CEOI18_clo)	C++17	100 / 100	391 ms	1412 KiB

clo

#include <bits/stdc++.h>

using namespace std;

constexpr int N = (int)7e5;

void solve(){
	int n;
	cin >> n;

	int c[n],f[n],v[n];
	for(int i = 0; i < n; i++){
		cin >> c[i] >> f[i] >> v[i];
	}

	int m;
	cin >> m;

	int C[m],F[m],V[m];
	int sumOrderC = 0;

	for(int i = 0; i < m; i++){
		cin >> C[i] >> F[i] >> V[i];
		sumOrderC += C[i];
	}

	{
		vector<int> s;
		for(int i = 0; i < m; i++){
			s.push_back(F[i]);
		}
		s.push_back(0);
		sort(s.begin(),s.end());
		s.erase(unique(s.begin(),s.end()),s.end());
		for(int i = 0; i < n; i++){
			f[i] = *(upper_bound(s.begin(),s.end(),f[i]) - 1);
		}
		for(int i = 0; i < n; i++){
			f[i] = lower_bound(s.begin(),s.end(),f[i]) - s.begin();
		}
		for(int i = 0; i < m; i++){
			F[i] = lower_bound(s.begin(),s.end(),F[i]) - s.begin();
		}
		// cerr << "debug:\n";
		// for(int i = 0; i < n; i++){
		// 	cerr << c[i] << " " << f[i] << " " << v[i] << "\n";
		// }
		// cerr << "\n";
		// for(int i = 0; i < m; i++){
		// 	cerr << C[i] << " " << F[i] << " " << V[i] << "\n";
		// }
		// cerr << "\n";
	}

	vector<pair<int,int>> computers[m+1];
	vector<pair<int,int>> orders[m+1];

	for(int i = 0; i < n; i++){
		computers[f[i]].push_back(make_pair(c[i],v[i]));
	}
	for(int i = 0; i < m; i++){
		orders[F[i]].push_back(make_pair(C[i],V[i]));
	}

	long long dp[sumOrderC+1];
	memset(dp,0,sizeof dp);

	for(int i = 0; i <= m; i++){
		for(auto&[cores,value] : orders[i]){
			for(int j = sumOrderC; j - cores >= 0; j--){
				dp[j] = max(dp[j],dp[j-cores]+value);
			}
		}
		for(auto&[cores,value] : computers[i]){
			for(int j = 0; j <= sumOrderC; j++){
				dp[max(0,j-cores)] = max(dp[max(0,j-cores)],dp[j]-value);
			}
		}
	}

	cout << dp[0] << "\n";

	return;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int tests = 1;
	for(int test = 1; test <= tests; test++){
		solve();
	}

	return 0;
}
/**
 * dist(1,2) = (a[1] != a[2]) + (a[2] != a[3]) + (a[3] != a[4]) + ... + (a[l] != a[l+1])
 * dist(1,3) = (a[1] != a[3]) + (a[2] != a[4])
 * 
 * 
 * 

**/

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