Submission #492407

#	Time	Username	Problem	Language	Result	Execution time	Memory
492407		niloyroot	Cloud Computing (CEOI18_clo)	C++14	36 / 100	119 ms	262148 KiB

clo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
#define ff first
#define ss second
const ll mod = 1e9 + 7;
 
struct comp {
    ll c,f,v;
};
 
bool cmp(comp a, comp b){
    return a.f != b.f ? a.f > b.f : a.v < b.v;
}
 
void solve(){
    ll n; cin>>n;
    vector<comp> comps;
    comp cp; cp.c=0; cp.f=INT_MAX; cp.v=0; comps.pb(cp);
    ll maxc=0;
    forp(i,1,n){
        cin>>cp.c>>cp.f>>cp.v;
        cp.v*=-1;
        comps.pb(cp);
        maxc+=cp.c;
    }
    ll m; cin>>m;
    forp(i,1,m){
        cin>>cp.c>>cp.f>>cp.v;
        cp.c*=-1;
        comps.pb(cp);
    }
    sort(comps.begin(), comps.end(), cmp);
 
    ll dp[n+m+1][maxc+1];
    forp(i,0,n+m){
        forp(j,0,maxc){
            dp[i][j]=INT64_MIN;
        }
    }
    dp[0][0]=0;
 
    ll res=0;
    forp(i,1,n+m){
        forp(j,0,maxc){
            if(j-comps[i].c>=0 && j-comps[i].c<=maxc && dp[i-1][j-comps[i].c]!=INT64_MIN){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-comps[i].c]+comps[i].v);
            } else {
                dp[i][j]=dp[i-1][j];
            }
            res=max(res,dp[i][j]);
        }
    }
 
    cout<<res<<newl;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1; //cin>>t;
    while(t--)solve();
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 18
• Subtask 3: 18 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10