Submission #1237884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237884		NeilP	Cloud Computing (CEOI18_clo)	C++20	0 / 100	48 ms	584 KiB

clo

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

                              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;

int dp1[10001];
int dp2[10001];

bool bp1[10001];
bool bp2[10001];
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 < 10001; j++){
            if(bp1[j]) bp2[j] = true;
            if(j + cores >= 0 && j + cores < 10001){
                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 < 10001; j++){
            dp1[j] = dp2[j];
            bp1[j] = bp2[j];
        }
    }
    
    int ans = 0;
    for(int i = 0; i < 10001; i++){
        if(dp1[i] > ans) ans = dp1[i];
    }
    cout << ans << endl;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10