Submission #972888

#	Time	Username	Problem	Language	Result	Execution time	Memory
972888		Gajowy	Cloud Computing (CEOI18_clo)	C++17	100 / 100	974 ms	2132 KiB

clo

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fwd(i, a, n) for (int i = (a); i < (n); i ++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define vi vector<int>
#define pii pair<int, int>
#define ll long long
#define vll vector<long long>

#ifdef LOC
auto &operator<<(auto &out, pair<auto, auto> a) {
    return out << "(" << a.st << ", " << a.nd << ")";
}
auto &operator<<(auto &out, auto a) {
    out << "{";
    for (auto b : a)
        out << b << ", ";
    return out << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif

const int maxN = 2000 + 10;
const int maxC = 100;
const ll inf = 1e18;

struct computer {
    int c, f, v;
    computer() {}
    computer(int c, int f, int v) : c(c), f(f), v(v) {}
};

struct order {
    int c, f, v;
    order() {}
    order(int c, int f, int v) : c(c), f(f), v(v) {}
};

computer comp[maxN];
order ord[maxN];

ll dp[maxN][maxC + 1];

void fix(int cid, int m) {
    rep(i, m) {
        rep(j, maxC + 1)
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        if (ord[i + 1].f > comp[cid].f) continue;
        for (int j = ord[i + 1].c; j <= maxC; j ++) {
            dp[i + 1][j - ord[i + 1].c] = max(
                dp[i + 1][j - ord[i + 1].c],
                dp[i][j] + ord[i + 1].v
            );
        }
    }
}

void ext(int cid, int m) {
    rep(i, m + 1)
        for (int j = maxC; j >= 0; j --) {
            int s = min(maxC, j + comp[cid].c);
            dp[i][s] = max(dp[i][s], dp[i][j] - comp[cid].v);
        }
}

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int c, f, v;
        cin >> c >> f >> v;
        comp[i] = computer(c, f, v);
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; i ++) {
        int c, f, v;
        cin >> c >> f >> v;
        ord[i] = order(c, f, v);
    }
    sort(comp + 1, comp + n + 1, [&](auto &a, auto &b) {
        return a.f > b.f;
    });
    sort(ord + 1, ord + m + 1, [&](auto &a, auto &b) {
        return a.f > b.f;
    });
    rep(i, m + 1)
        fill(dp[i], dp[i] + maxC + 1, -inf);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i ++) {
        ext(i, m);
        fix(i, m);
    }
    cout << *max_element(dp[m], dp[m] + maxC + 1) << '\n';
}

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