제출 #916951

#제출 시각아이디문제언어결과실행 시간메모리
916951ThommyDBCloud Computing (CEOI18_clo)C++17
36 / 100
3102 ms262144 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;
map<pair<int, int>, int> memo;

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

int DP(int x, int computers){
    if(memo.find({x, computers}) != memo.end()){
        return memo[{x, computers}];
    }

    if(computers < 0) return -1e10;
    if(x== n+m) return 0;

    int ans = max(DP(x+1, computers), DP(x+1, computers+computersAndOrders[x].cores)+computersAndOrders[x].price);
    memo[{x, computers}] = ans;
    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(), increaseF);

    cout << DP(0, 0) << "\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...