Submission #775878

#	Time	Username	Problem	Language	Result	Execution time	Memory
775878		Dzadzo	Cloud Computing (CEOI18_clo)	C++17	0 / 100	91 ms	262144 KiB

clo

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vector<int>>
#define INF LLONG_MAX
#define MOD 1000000009
#define MAXN 2000
#define MAXM 2000
using namespace std;
int c[MAXN+MAXM+1],f[MAXN+MAXM+1],v[MAXN+MAXM+1];
bool comp(int a,int b){
	if (f[a]>f[b])return true;
	if (f[a]<f[b])return false;
	return v[a]<v[b];
}
main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
//	freopen("problemname.in", "r", stdin);
//	freopen("problemname.out", "w", stdout);
	int n;
	cin>>n;
	
	for (int i=1;i<=n;i++){
		int q1,q2,q3;
		cin>>q1>>q2>>q3;
		c[i]=q1;
		f[i]=q2;
		v[i]=-q3;
	}
	int m;
	cin>>m;
	for (int i=n+1;i<=n+m;i++){
		int q1,q2,q3;
		cin>>q1>>q2>>q3;
		c[i]=-q1;
		f[i]=q2;
		v[i]=q3;		
	}
	int ind[n+m+1];
	for (int i=1;i<=n+m;i++)ind[i]=i;
	sort(ind+1,ind+n+m+1,comp);
	vvi dp(n+m+1,vi (MAXN*50+51,-INF));
	dp[0][0]=0;
	
	for (int i=1;i<=n+m;i++){
		for (int k=0;k<=MAXN*50+50;k++){
			dp[i][k]=max(dp[i][k],dp[i-1][k]);
			if (k-c[ind[i]]>=0 && k-c[ind[i]]<=MAXN*50+50){
				if (dp[i-1][k-c[ind[i]]]!=-INF){
					dp[i][k]=max(dp[i][k],dp[i-1][k-c[ind[i]]]+v[ind[i]]);
				}
			}	
		}
	}
//	for (int i=1;i<=n+m;i++)cout<<c[ind[i]]<<" "<<f[ind[i]]<<" "<<v[ind[i]]<<"\n";
	int ans=0;
	for (int i=0;i<=MAXN*50+50;i++)ans=max(ans,dp[n+m][i]);
/*	for (int i=1;i<=n+m;i++){
		cout<<"---"<<i<<"---\n";
		for (int k=0;k<=MAXN*50;k++){
			if (dp[i][k]!=-INF)
			cout<<k<<" "<<dp[i][k]<<"\n";
		}
		cout<<"\n";
	}
	*/
	cout<<ans;
}

Compilation message (stderr)

clo.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~

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