제출 #975988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975988		irmuun	Cloud Computing (CEOI18_clo)	C++17	100 / 100	378 ms	1620 KiB

clo

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    vector<array<ll,4>>v;
    for(ll i=1;i<=n;i++){
        ll c,f,u;
        cin>>c>>f>>u;
        v.pb({f,1,c,u});
    }
    ll m;
    cin>>m;
    for(ll i=1;i<=m;i++){
        ll c,f,u;
        cin>>c>>f>>u;
        v.pb({f,0,c,u});
    }
    sort(rall(v));
    vector<ll>dp(2000*50+5,-1e18);//balance
    dp[0]=0;
    for(auto [f,t,c,u]:v){
        if(t==1){
            for(ll i=2000*50;i>=0;i--){
                if(i-c>=0){
                    dp[i]=max(dp[i],dp[i-c]-u);
                }
            }
        }
        else{
            for(ll i=0;i<=2000*50;i++){
                if(i-c>=0){
                    dp[i-c]=max(dp[i-c],dp[i]+u);
                }
            }
        }
    }
    ll ans=0;
    for(ll i=0;i<=2000*50;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

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