Submission #819882

#	Time	Username	Problem	Language	Result	Execution time	Memory
819882		nstefan	Cloud Computing (CEOI18_clo)	C++17	54 / 100	532 ms	2516 KiB

clo

#include <algorithm>
#include <bits/stdc++.h>
#ifdef N257
std::ifstream fin("input.in");
#define cin fin
#else
// std::ifstream fin    (".in");
// std::ofstream fout   (".out");
// #define cin fin
// #define cout fout
#endif
using namespace std;

#define VEC(T, N, V) vector<T>(N, V)
#define MAT(T, N, M, V) vector<vector<T>>(N, vector<T>(M, V))
#define CUBE(T, N, M, L, V) vector<vector<vector<T> > >(N, vector<vector<T> >(M, vector<T>(L, V)))

#define sz(a) (int)((a).size())
#define all(a) begin(a), end(a)
#define endl '\n'
#define int long long
#define dbg(x) cerr << "[DEBUG] " << #x << ": " << x << '\n'

const int inf = 1e18;
const int mod = 1e9 + 7;

struct Transaction {
    int deltaCores = 0;
    int freqRate = 0;
    int deltaProfit = 0;

    bool operator<(const Transaction &other) const {
        return other.freqRate == freqRate ? other.deltaProfit < deltaProfit : other.freqRate < freqRate;
    }
};

signed main() {
    int N, M, max_cores = 0;
    vector<Transaction> transactions;

    // reading computers
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int c, f, v; cin >> c >> f >> v;
        max_cores += c;
        transactions.push_back({c, f, -v});
    }

    // reading orders
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int c, f, v; cin >> c >> f >> v;
        transactions.push_back({-c, f, v});
    }

    sort(all(transactions));

    // for (auto &t : transactions) {
    //     cout << t.deltaCores << " " << t.freqRate << " " << t.deltaProfit << endl;
    // }

    
    // dp[t][c] = maximum profit gained if
    //  * we take into account the first ``t`` transactions
    //  * we have ``c`` cores left
    auto dp = MAT(int, 2, max_cores + 1, -inf);
    
    dp[0][0] = 0;

    for (int t = 1; t <= transactions.size(); ++t) {
        for (int c = 0; c <= max_cores; ++c) {
            // do not take the transaction
            dp[t % 2][c] = max(dp[t % 2][c], 
                dp[(t - 1) % 2][c]);

            // take the transaction
            if (0 <= c - transactions[t - 1].deltaCores and
                c - transactions[t - 1].deltaCores <= max_cores and
                dp[(t - 1) % 2][c - transactions[t - 1].deltaCores] != -inf)
                    dp[t % 2][c] = max(dp[t % 2][c],
                        dp[(t - 1) % 2][c - transactions[t - 1].deltaCores] + transactions[t - 1].deltaProfit);
        }
    }


    cout <<  *max_element(dp[(N + M) % 2].begin(), dp[(N + M) % 2].end()) << endl;


}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:70:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Transaction>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int t = 1; t <= transactions.size(); ++t) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~

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