Submission #917282

#TimeUsernameProblemLanguageResultExecution timeMemory
917282ThommyDBCloud Computing (CEOI18_clo)C++17
100 / 100
1162 ms3924 KiB
#include<bits/stdc++.h>

using namespace std;
#define int long long

struct ComputersAndOrders{
    int cores;
    int clockSpeed;
    int price;
};

int n, m;
vector<ComputersAndOrders> computersAndOrders;

bool decreaseF(const ComputersAndOrders a, const ComputersAndOrders b){
    if(a.clockSpeed == b.clockSpeed){
        if(a.price==b.price){
            return a.price > b.price;
        }
        return a.cores > b.cores;
    }
    return a.clockSpeed > b.clockSpeed;
}

int DP(){
    vector<int> memo(1e5*2, -1e15);
    vector<int> mem;
    memo[0]=0;
    mem.assign(memo.begin(), memo.end());

    for(int i = 0; i < n+m; i++){
        for(int j = 0; j < 1e5*2; j++){
            if(memo[j] > -1e15 && j+computersAndOrders[i].cores>=0){
                mem[j+computersAndOrders[i].cores] = max(memo[j+computersAndOrders[i].cores], memo[j]+computersAndOrders[i].price);
            }
        }

        memo.clear();
        memo.assign(mem.begin(), mem.end());
    }

    int ans = 0;
    for(int i = 0; i < 1e5*2; i++){
        ans = max(ans, memo[i]);
    }

    return ans;
}

signed main(){
    cin >> n;
    computersAndOrders.resize(n);
    int c, f, v;
    for(int i = 0; i <n; i++){
        cin >> c >> f >> v;
        computersAndOrders[i].cores = c;
        computersAndOrders[i].clockSpeed = f;
        computersAndOrders[i].price = -v;
    }
    cin >> m;
    computersAndOrders.resize(n+m);
    for(int i = 0; i < m; i++){
        cin >> c >> f >> v;
        computersAndOrders[i+n].cores = -c;
        computersAndOrders[i+n].clockSpeed = f;
        computersAndOrders[i+n].price = v;
    }
    sort(computersAndOrders.begin(), computersAndOrders.end(), decreaseF);

    cout << DP() << "\n";
}
#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...