Submission #599706

#	Time	Username	Problem	Language	Result	Execution time	Memory
599706		CSQ31	Cloud Computing (CEOI18_clo)	C++17	100 / 100	528 ms	1556 KiB

clo

#pragma GCC optimization ("O3")
#include <bits/stdc++.h>
using namespace std;
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
const int MAXN = 1e5+5;
ll dp1[MAXN];
int c[2][2000],f[2][2000],v[2][2000];
vector<int>buy[4000],sell[4000];
int main()
{
	owo
	int n;
	cin>>n;
	vector<int>crd;
	bool ok = 1;
	int mx = 0;
	for(int i=0;i<n;i++){
		cin>>c[0][i]>>f[0][i]>>v[0][i];
		crd.push_back(f[0][i]);
		mx = max(c[0][i],mx);
		if(f[0][i] != 1)ok = 0;
	}
	int m;cin>>m;
	for(int i=0;i<m;i++){
		cin>>c[1][i]>>f[1][i]>>v[1][i];
		crd.push_back(f[1][i]);
		mx = max(c[1][i],mx);
		if(f[1][i] != 1)ok = 0;
	}
	int mxx = mx*n;
	for(int i=1;i<=mxx;i++)dp1[i] = -1e13;
	dp1[0] = 0;
	if(ok){
		for(int i=0;i<n;i++){
			for(int j=mxx;j>=c[0][i];j--){
				if(dp1[j-c[0][i]] != -1e13)dp1[j] = max(dp1[j],dp1[j-c[0][i]] - v[0][i]);
				
			}
		}
		for(int i=0;i<m;i++){
			for(int j=0;j + c[1][i]<=mxx;j++){
				if(dp1[j + c[1][i]] != -1e13)dp1[j] = max(dp1[j + c[1][i]] + v[1][i],dp1[j]);
			}	
			
		}
		ll ans = 0;
		for(int i=0;i<=mxx;i++)ans = max(dp1[i],ans);
		cout<<ans<<'\n';
		
	}else{
		sort(crd.begin(),crd.end());
	    crd.resize(unique(crd.begin(),crd.end()) - crd.begin());
		for(int i=0;i<n;i++){
			f[0][i] = lower_bound(crd.begin(),crd.end(),f[0][i]) - crd.begin();
			buy[f[0][i]].push_back(i);
		}
		for(int i=0;i<m;i++){
			f[1][i] = lower_bound(crd.begin(),crd.end(),f[1][i]) - crd.begin();
			sell[f[1][i]].push_back(i);
			
		}
		for(int i=3999;i>=0;i--){
			if(buy[i].empty() && sell[i].empty())continue;
			for(int x:buy[i]){
				for(int i=mxx;i>=c[0][x];i--){
					if(dp1[i - c[0][x]] != -1e13)dp1[i] = max(dp1[i-c[0][x]] - v[0][x],dp1[i]);
				}	
			}
			for(int x:sell[i]){
				for(int i=0;i + c[1][x]<=mxx;i++){
					if(dp1[i + c[1][x]] != -1e13)dp1[i] = max(dp1[i + c[1][x]] + v[1][x],dp1[i]);
				}	
			}
		}
		ll ans = 0;
		for(int i=0;i<=mxx;i++)ans = max(ans,dp1[i]);
			cout<<ans<<'\n';
	}
	
	
	
}

Compilation message (stderr)

clo.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      |

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