Submission #1303201

#TimeUsernameProblemLanguageResultExecution timeMemory
1303201dex111222333444555Cloud Computing (CEOI18_clo)C++20
100 / 100
598 ms2292 KiB
#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
using namespace std;

template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}

const int MAXN = 2005, MAXC = 55, infINT = 1e9 + 23432;
const long long inf = 1e18 + 234;

struct com{
    int core, func, cost;
    bool type;

    com(int _core = 0, int _func = 0, int _cost = 0, bool _type = 0):
        core(_core), func(_func), cost(_cost), type(_type) {};

    bool operator<(const com &other){
        return (func > other.func) || (func == other.func && type < other.type);
    }
};

int numCom, numQuery;
long long dp[2][MAXN * MAXC];
vector<com> vals;

void input(){
    vals.push_back(com(0, infINT, 0, 0));

    cin >> numCom;
    for(int i = 1; i <= numCom; i++){
        int core, func, cost;
        bool type = 0;
        cin >> core >> func >> cost;
        vals.push_back(com(core, func, cost, type));
    }

    cin >> numQuery;
    for(int q = 1; q <= numQuery; q++){
        int core, func, cost;
        bool type = 1;
        cin >> core >> func >> cost;
        vals.push_back(com(core, func, cost, type));
    }
}

void solve(){
    sort(all(vals));

    memset(dp[0], -0x3f, sizeof dp[0]);
    int cur = 1, nxt = 0;

    dp[0][0] = 0;
    for(int i = 0; i < numCom + numQuery; i++){
        swap(cur, nxt);
        memset(dp[nxt], -0x3f, sizeof dp[nxt]);

        for(int sum = 0; sum < MAXN * MAXC; sum++) if (dp[cur][sum] > -inf){
            maximize(dp[nxt][sum], dp[cur][sum]);

            if (vals[i + 1].type == 0 && sum + vals[i + 1].core < MAXN * MAXC)
                maximize(dp[nxt][sum + vals[i + 1].core], dp[cur][sum] - vals[i + 1].cost);

            if (vals[i + 1].type == 1 && sum - vals[i + 1].core >= 0)
                maximize(dp[nxt][sum - vals[i + 1].core], dp[cur][sum] + vals[i + 1].cost);
        }
    }

    long long res = 0;

    for(long long x: dp[nxt]) maximize(res, x);

    cout << res << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "tests"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    input();
    solve();
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...