Submission #472979

#TimeUsernameProblemLanguageResultExecution timeMemory
472979fadi57Cloud Computing (CEOI18_clo)C++17
100 / 100
931 ms2060 KiB
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int mx=2009;
typedef long long ll;
 int mod=1e9+7;
const int MXm=22;
#define F first
#define S second
const ll inf=1e14+10;
int n,m;
struct computer{
ll c,f,v,typ;
};

ll dp[2000*50+90][2];computer a[mx+mx];
 bool cmp(computer x,computer y){

   if(x.f!=y.f){

     return x.f>y.f;

   }else{
    return x.typ<y.typ;

    }}

 int main(){
   cin>>n;
   ll sum=0;

   for(int i=0;i<n;i++){
   cin>>a[i].c>>a[i].f>>a[i].v;
     sum+=a[i].c;
    a[i].typ=0;
   }
   cin>>m;
    for(int i=n;i<m+n;i++){

    cin>>a[i].c>>a[i].f>>a[i].v;
     a[i].typ=1;
   }
    sort(a,a+(n+m),cmp);

    for(int i=0;i<=sum;i++){

        dp[i][1]=-inf;
    }
    dp[0][1]=0;  ll ans=0;

    for(int i=0;i<n+m;i++){

        for(int j=0;j<=sum;j++){

            dp[j][i&1]=dp[j][(i+1)&1];
            if(a[i].typ==0){
                if(j-a[i].c>=0){
                    dp[j][i&1]=max(dp[j-a[i].c][(i+1)&1]-a[i].v,dp[j][i&1]);
                }

            }else{

            if(a[i].c+j<=sum){
                    dp[j][i&1]=max(dp[j+a[i].c][(i+1)&1]+a[i].v,dp[j][i&1]);
                }


            }

      ans=max(ans,dp[j][i&1]);

        }


    }
 cout<<ans;
    }
#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...