제출 #569553

#제출 시각아이디문제언어결과실행 시간메모리
569553tarunares7250Cloud Computing (CEOI18_clo)C++17
72 / 100
501 ms1420 KiB
//ulimit -s unlimited
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define vl vector<ll>
#define vi vector<int>
#define vb vector<bool>
#define pql priority_queue<long long>
#define pqp priority_queue<pair<ll,ll> >
#define pqs priority_queue<ll,vl,greater<ll> >
#define md ((ll) 1e9+7)


typedef struct node{
    ll c,f,v;
    bool operator<(node &b) const{
        return (f>b.f);
    }
}node;

void solve(){

    ll i,j,k,n,m;
    cin>>n;
    vector<node> sc(n);
    vector<node> a;
    ll tc = 0;
    for(i=0;i<n;i++){
        cin>>sc[i].c>>sc[i].f>>sc[i].v;
        sc[i].v *= -1;
        a.push_back(sc[i]);
        tc += sc[i].c;
    }
    cin>>m;
    vector<node> oc(m);
    for(i=0;i<m;i++){
        cin>>oc[i].c>>oc[i].f>>oc[i].v;
        oc[i].c *= -1;
        a.push_back(oc[i]);
    }
    sort(a.begin(),a.end());

    ll dp[tc+1];
    bool isp[tc+1];
    memset(isp,false,sizeof(isp));
    for(i=0;i<=tc;i++){
        dp[i] = -1e15;
    }
    dp[0] = 0;
    isp[0] = true;
    for(i=0;i<n+m;i++){
        if(a[i].c>0){
            for(j=tc;j>=a[i].c;j--){
                if(isp[j-a[i].c]){
                    dp[j] = max(dp[j],dp[j-a[i].c]+a[i].v);
                    isp[j] = true;
                }
            }
        }
        else{
            for(j = 0;j<=tc+a[i].c;j++){
                if(isp[j-a[i].c]){
                    dp[j] = max(dp[j],dp[j-a[i].c]+a[i].v);
                    isp[j] = true;
                }
            }
        }
    }

    ll ans = 0;
    for(i=0;i<=tc;i++){
        ans = max(ans,dp[i]);
    }
    cout<<ans<<"\n";

    // for(auto c:a){
    //     cout<<c.c<<","<<c.f<<","<<c.v<<"\n";
    // }


}
/*

dp[i][j][k] = max profit till ith computer and jth order,k cores 
are remaining
dp[i-1][j] , dp[j][i-1] ,  dp[i-1][j-1]

*/
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    //cin >> t;
    t = 1;
    while(t--)
        solve();
    return 0;
}

/*
ll i,j,k,n,m;
    cin>>n;
    vector<node> sp(n);
    for(i=0;i<n;i++){
        cin>>sp[i].c>>sp[i].f>>sp[i].v;
    }
    sort(sp.begin(),sp.end());

    cin>>m;
    vector<node> od(m);
    for(i=0;i<m;i++){
        cin>>od[i].c>>od[i].f>>od[i].v;
    }
    sort(od.begin(),od.end());
    
    vector<vector<vl> > dp(n,vector<vl> (m,vl(51,0)));
    //dp[0][0][0] = 0;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            for(k=0;k<51;k++){
                dp[i][j][k] = max({(j-1>=0?dp[i][j-1][k]:0),(i-1>=0?dp[i-1][j][k]:0),
                ((i-1>=0 && j-1>=0 && k-(sp[i].c - od[j].c)>=0 && sp[i].f>=od[j].f)?dp[i-1][j-1][k-(sp[i].c - od[j].c)] + od[j].v-sp[i].v:0),
                });
            }
        }
    }

    ll ans = 0;
    for(k=0;k<=50;k++){
        ans = max(ans,dp[n-1][m-1][k]);
    }
    cout<<ans<<"\n";

    cout<<"sp"<<"\n";
    for(i=0;i<n;i++){
        cout<<sp[i].c<<","<<sp[i].f<<","<<sp[i].v<<"\n";
    }
    cout<<"od\n";
    for(i=0;i<m;i++){
        cout<<od[i].c<<","<<od[i].f<<","<<od[i].v<<"\n";
    }
    cout<<dp.size()<<"\n";
    cout<<dp[0].size()<<"\n";
    cout<<dp[0][0].size()<<"\n";

*/

컴파일 시 표준 에러 (stderr) 메시지

clo.cpp: In function 'void solve()':
clo.cpp:23:12: warning: unused variable 'k' [-Wunused-variable]
   23 |     ll i,j,k,n,m;
      |            ^
#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...