제출 #819847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
819847		nstefan	Cloud Computing (CEOI18_clo)	C++17	36 / 100	96 ms	262144 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;
    }
};

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, transactions.size() + 1, 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][c] = max(dp[t][c], 
                dp[t - 1][c]);

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


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


}

컴파일 시 표준 에러 (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: 0 / 18
• Subtask 6: 0 / 10