Submission #1006073

#TimeUsernameProblemLanguageResultExecution timeMemory
1006073KindaNamelessCloud Computing (CEOI18_clo)C++14
100 / 100
350 ms1468 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

struct item{
    int cores, clock_rate; ll value; bool flag;

    item(int _cores, int _clock_rate, ll _value, bool _flag){
        cores = _cores;
        clock_rate = _clock_rate;
        value = _value;
        flag = _flag;
    }

    bool operator < (const item &other) const {
        if(clock_rate == other.clock_rate){
            return flag < other.flag;
        }
        return clock_rate < other.clock_rate;
    }
};

ll dp[100001];

void solve(){
    int n; cin >> n;

    vector<item> comp;
    for(int i = 1; i <= n; ++i){
        int c, f, v; cin >> c >> f >> v;
        comp.push_back(item(c, f, v, 1));
    }

    int m; cin >> m;

    for(int i = 1; i <= m; ++i){
        int C, F, V; cin >> C >> F >> V;
        comp.push_back(item(C, F, V, 0));
    }

    sort(comp.begin(), comp.end());
    reverse(comp.begin(), comp.end());

    for(int i = 1; i <= 100000; ++i){
        dp[i] = -1e18;
    }

    ll answer = 0;
    for(item elem : comp){
        //cout << elem.flag << " " << elem.clock_rate << "\n";
        if(elem.flag){
            for(int j = 100000; j >= 1; --j){
                dp[j] = max(dp[j], dp[max(0, j - elem.cores)] - elem.value);
            }
        }
        else{
            for(int j = 0; j <= 100000 - elem.cores; ++j){
                dp[j] = max(dp[j], dp[j + elem.cores] + elem.value);
                answer = max(answer, dp[j]);
            }
        }
    }

    cout << answer;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1; //cin >> tc;

    while(tc--){
        solve();
    }

    return 0;
}
#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...