Submission #470881

#	Time	Username	Problem	Language	Result	Execution time	Memory
470881		SansPapyrus683	Cloud Computing (CEOI18_clo)	C++17	18 / 100	798 ms	1836 KiB

clo

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

// #include "debugging.h"

using std::cout;
using std::endl;
using std::vector;

struct Transaction {
    int cores;
    int rate;
    int price;
};

/**
 * https://oj.uz/problem/view/CEOI18_clo
 * 4
 * 4 2200 700
 * 2 1800 10
 * 20 2550 9999
 * 4 2000 750
 * 3
 * 1 1500 300
 * 6 1900 1500
 * 3 2400 4550 should output 350
 */
int main() {
    vector<Transaction> poss_transactions;
    int max_computers = 0;
    int comp_num;
    std::cin >> comp_num;
    for (int c = 0; c < comp_num; c++) {
        Transaction trans;
        std::cin >> trans.cores >> trans.rate >> trans.price;
        trans.price = -trans.price;
        poss_transactions.push_back(trans);
        max_computers += trans.cores;
    }
    int order_num;
    std::cin >> order_num;
    for (int o = 0; o < order_num; o++) {
        Transaction trans;
        std::cin >> trans.cores >> trans.rate >> trans.price;
        trans.cores = -trans.cores;
        poss_transactions.push_back(trans);
    }
    /*
     * if we sort like this, then the entire clock rate issue
     * goes away as long as we process them in order
     */
    std::sort(
        poss_transactions.begin(), poss_transactions.end(),
        [] (const Transaction& a, const Transaction& b) -> bool {
            return a.rate > b.rate;
        }
    );

    vector<long long> max_profits(max_computers + 1, INT64_MIN);
    max_profits[0] = 0;
    for (const Transaction& t : poss_transactions) {
        vector<long long> new_max(max_profits);
        for (int c = 1; c <= max_computers; c++) {
            int prev_comp = c - t.cores;
            if (0 <= prev_comp && prev_comp <= max_computers
                    && max_profits[prev_comp] != INT64_MIN) {
                new_max[c] = std::max(new_max[c], max_profits[prev_comp] + t.price);
            }
        }
        max_profits = new_max;
    }
    cout << *std::max_element(max_profits.begin(), max_profits.end()) << endl;
}

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