Submission #161231

#	Time	Username	Problem	Language	Result	Execution time	Memory
161231		rama_pang	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1012 ms	2168 KiB

clo

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e15;

struct item {   // standard DP Knapsack by reducing the problem to:
    int core;   // customer negative, shop positive - must be >= 0
    int clock;  // sort by this descendingly - then we can forget it
    int price;  // customer positive, shop negative - maximize this
    int type;   // 1 = shop, 2 = customer
};

int N, M;
item A[5005];
lint DP[2][100005]; // pos and current cores available

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N; for (int i = 0; i < N; i++) cin >> A[i].core >> A[i].clock >> A[i].price;
    cin >> M; for (int i = N; i < N + M; i++) cin >> A[i].core >> A[i].clock >> A[i].price;
    for (int i = 0; i < N; i++) A[i].type = 1;
    for (int i = N; i < N + M; i++) A[i].type = 2;

    sort(A, A + N + M, [&](item l, item r) { return l.clock > r.clock || (l.clock == r.clock && l.type < r.type); });
    for (int i = 0; i < N + M; i++) {
        if (A[i].type == 1) A[i].price *= -1;
        if (A[i].type == 2) A[i].core *= -1;
    }

    /* Base Case */
    for (int pos = 0; pos < 2; pos++) for (int core = 0; core <= 100000; core++) DP[pos][core] = -INF;
    DP[0][0] = 0;
    /* DP Knapsack */
    for (int pos = 0; pos < N + M; pos++) {
        for (int core = 0; core <= 100000; core++) {
            int nxt_core = core + A[pos].core;
            if (nxt_core >= 0) DP[(pos + 1) % 2][nxt_core] = max(DP[(pos + 1) % 2][nxt_core], DP[pos % 2][core] + A[pos].price);
            DP[(pos + 1) % 2][core] = max(DP[(pos + 1) % 2][core], DP[pos % 2][core]);
            DP[pos % 2][core] = -INF;
        }
        lint ans = -INF;
    }

    lint ans = 0;
    for (int core = 0; core <= 100000; core++) ans = max(ans, DP[(N + M) % 2][core]);
    cout << ans << "\n";
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:43:14: warning: unused variable 'ans' [-Wunused-variable]
         lint ans = -INF;
              ^~~

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