제출 #1269812

#제출 시각아이디문제언어결과실행 시간메모리
1269812datluong_04Cloud Computing (CEOI18_clo)C++20
100 / 100
648 ms2120 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define maxn 200005
#define FOR(i , a , b) for(int i = a ; i <= b; i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

struct Transaction{
    int cores;
    ll f , cost;
};

bool cmp(const Transaction &a , const Transaction &b){
    if(a.f == b.f) return a.cost < b.cost;
    return a.f > b.f;
}

int main(){
    FAST;
    int n , m;
    cin >> n;

    vector<Transaction> a;
    // buy a computer
    int max_cores = 0;
    FOR(i , 0 , n - 1){ 
        Transaction t;
        cin >> t.cores >> t.f >> t.cost;
        max_cores += t.cores;
        t.cost = -t.cost;
        a.push_back(t);
    }

    cin >> m;
    FOR(i , 0 , m - 1){
        Transaction t;
        cin >> t.cores >> t.f >> t.cost;
        max_cores += t.cores;
        t.cores = -t.cores;
        a.push_back(t);
    }

    sort(a.begin() , a.end() , cmp);
    vector<ll> dp(max_cores + 1);
    FOR(i , 0 , max_cores) dp[i] = -1e18;
    dp[0] = 0;
    for(const Transaction &x : a){
        // buy a computer
        if(x.cores > 0){
            for(int j = max_cores ; j >= 0 ; j--){
                if(j - x.cores >= 0 && dp[j - x.cores] != -1e18) dp[j] = max(dp[j] , dp[j - x.cores] - abs(x.cost)); 
            }
        }
        else{
            FOR(j , 0 , max_cores){
                if(j + abs(x.cores) < max_cores && dp[j + abs(x.cores)] != -1e18) dp[j] = max(dp[j] , dp[j + abs(x.cores)] + abs(x.cost)); 
            }
        }
    }

    ll ans = 0;
    FOR(i , 0 , max_cores) ans = max(ans , dp[i]);
    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...