제출 #1237886

#제출 시각아이디문제언어결과실행 시간메모리
1237886NeilPCloud Computing (CEOI18_clo)C++20
18 / 100
603 ms2228 KiB
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

long long dp1[100001];
long long dp2[100001];

bool bp1[100001];
bool bp2[100001];
int n, m;

struct order{
    bool comp;
    int cores;
    int freq;
    int price;
    
    order(bool a, int b, int c, int d){
        comp = a; cores = b; freq = c; price = d;
    }
};

bool comp(order a, order b){
    return a.freq > b.freq || ((a.freq == b.freq) && a.comp && !b.comp);
}

vector<order> orders;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        int c, f, v;
        cin >> c >> f >> v;
        orders.push_back({true, c, f, -v});
    }
    
    cin >> m;
    for(int i = 0; i < m; i++){
        int c, f, v;
        cin >> c >> f >> v;
        orders.push_back({false, -c, f, v});
    }
    
    sort(orders.begin(), orders.end(), comp);
    
    bp1[0] = true;
    
    for(int i = 0; i < m + n; i++){
        int cores = orders[i].cores;
        int value = orders[i].price;
        for(int j = 0; j < 100001; j++){
            if(bp1[j]) bp2[j] = true;
            if(j + cores >= 0 && j + cores < 100001){
                if((dp2[j + cores] < dp1[j] + value || !bp2[j+cores]) && bp1[j]){
                    dp2[j + cores] = dp1[j] + value;
                    bp2[j+cores] = true;
                }
            }
        }
        
        for(int j = 0; j < 100001; j++){
            dp1[j] = dp2[j];
            bp1[j] = bp2[j];
        }
    }
    
    int ans = 0;
    for(int i = 0; i < 100001; i++){
        if(dp1[i] > ans) ans = dp1[i];
    }
    cout << ans << endl;
}

#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...