Submission #658850

#TimeUsernameProblemLanguageResultExecution timeMemory
658850EthanKim8683Cloud Computing (CEOI18_clo)C++17
0 / 100
5 ms3488 KiB
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=2000;
const I M=2000;
const I C=50;
const Lli MIN=-1e18;
tuple<I,I,I>coms[N];
tuple<I,I,I>ords[M];
Lli dp[2][N][2*C+1];
void cmb(Lli&a,Lli b){
  a=max(a,b);
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  fill(&dp[0][0][0],&dp[0][0][0]+2*N*(2*C+1),MIN);
  I n;cin>>n;
  for(I i=0;i<n;i++){
    I c,f,v;cin>>c>>f>>v;
    coms[i]={f,c,v};
  }
  I m;cin>>m;
  for(I i=0;i<m;i++){
    I c,f,v;cin>>c>>f>>v;
    ords[i]={f,c,v};
  }
  sort(coms,coms+n);
  sort(ords,ords+m);
  Lli res=MIN;
  for(I i=0;i<m;i++){
    for(I j=0;j<n;j++){
      auto[fi,ci,vi]=ords[i];
      auto[fj,cj,vj]=coms[j];
      cmb(dp[i%2][j][0],-vj);
      for(I k=0;k<=cj;k++){
        if(fj>=fi)cmb(dp[(i+1)%2][j][k+ci],dp[i%2][j][k]+vi);
        cmb(dp[(i+1)%2][j][k],dp[i%2][j][k]);
        cmb(res,dp[i%2][j][k]);
      }
      if(j+1<n)for(I k=0;k<=2*C;k++)cmb(dp[i%2][j+1][max(k-cj,0)],dp[i%2][j][k]-get<2>(coms[j+1]));
    }
    for(I j=0;j<n;j++)for(I k=0;k<=2*C;k++)dp[i%2][j][k]=MIN;
  }
  for(I i=0;i<n;i++)for(I j=0;j<=get<1>(coms[i]);j++)cmb(res,dp[m%2][i][j]);
  printf("%lli\n",res);
}
#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...