Submission #975737

#	Time	Username	Problem	Language	Result	Execution time	Memory
975737		PM1	Cloud Computing (CEOI18_clo)	C++17	100 / 100	318 ms	1444 KiB

clo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=2e3+5,mxk=50;
int n,m;
struct server{
	ll f,c,v;
}s[mxn*2];
ll dp[mxn*mxk];
bool cmp(server x,server y){
	return (x.f!=y.f)? (x.f > y.f ):(x.c>y.c);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].c>>s[i].f>>s[i].v;
	}
	cin>>m;
	for(int i=n+1;i<=n+m;i++){
		cin>>s[i].c>>s[i].f>>s[i].v;
		s[i].c*=-1,s[i].v*=-1;
	}
	for(int i=1;i<mxn*mxk;i++)
		dp[i]=1e18;
	sort(s+1,s+n+m+1,cmp);
	for(int i=1;i<=n+m;i++){
		if(s[i].c>0){
			for(int j=mxn*mxk-1;j>=s[i].c;j--)
				dp[j]=min(dp[j],dp[j-s[i].c]+s[i].v);
		}
		else{
			for(int j=0;j<mxn*mxk+s[i].c;j++)
				dp[j]=min(dp[j],dp[j-s[i].c]+s[i].v);
		}
	}
	ll ans=0;
	for(int i=0;i<mxn*mxk;i++)
		ans=min(ans,dp[i]);
	cout<<-ans;
	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