Submission #1311162

#TimeUsernameProblemLanguageResultExecution timeMemory
1311162neonglitchCloud Computing (CEOI18_clo)C++20
54 / 100
3094 ms12332 KiB
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2008,UB=15*50+2;
typedef long long ll;
int c[N],f[N],v[N],C[N],F[N],V[N],ord[N],ord1[N];
ll dp[UB+2][N];
bool byf(int x,int y)
{
	return f[x]>f[y];
}
bool byF(int x,int y)
{
	return F[x]>F[y];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i]>>f[i]>>v[i];
		ord[i-1]=i;
	}
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>C[i]>>F[i]>>V[i];
		ord1[i-1]=i;
	}
	sort(ord,ord+n,byf);
	sort(ord1,ord1+m,byF);
	for(int i=0;i<=UB;i++)
	{
		for(int j=0;j<N;j++)
		{
			dp[i][j]=-1e18;
		}
	}
	dp[0][0]=0;
	for(int ia=0;ia<n;ia++)
	{
		int i=ord[ia];
		for(int ja=0;ja<=m;ja++)
		{
			for(int r=UB;r>=c[i];r--)
			{
				dp[r][ja]=max(dp[r][ja],dp[r-c[i]][ja] - v[i]); // we increase available cores but need to pay a price
			}			
		}
		for(int r=UB;r>=0;r--)
		{
			for(int ja=0;ja<m;ja++)
			{
				int j=ord1[ja];
				if(f[i]>=F[j] and r>=C[j])
				{
					dp[r-C[j]][ja+1]=max(dp[r-C[j]][ja+1],dp[r][ja] + V[j]); // customer buys
				}
				dp[r][ja+1]=max(dp[r][ja+1],dp[r][ja]); // customer doesn't buy
			}
		}
	}
	ll ans=0;
	for(int r=0;r<=UB;r++)
	{
		for(int ja=0;ja<=m;ja++)
		{
			ans=max(ans,dp[r][ja]);
		}
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...