← Real problems

ceoi18p1

mediumdpknapsacksortingStatement on DMOJ

CP Lang

15 lines0.3 spec
// CEOI 2018 "Cloud Computing": buy computers (cores, clock, price) and accept
// orders (cores, min clock, pay). Going down by clock, a core bought at a clock
// can serve any order at or below it: a knapsack over free cores.
let comps = read<List<(cores: 1..=50, clock: 1..=1e9, price: 1..=1e9)>>()
let orders = read<List<(cores: 1..=50, clock: 1..=1e9, pay: 1..=1e9)>>()
let deals = chain(
    comps.map(c => (clock: c.clock, order: false, cores: c.cores, cash: -c.price)),
    orders.map(o => (clock: o.clock, order: true, cores: -o.cores, cash: o.pay)),
).sorted(by: d => (desc(d.clock), d.order))

domain Free = 0..=comps.sum(of: .cores)
var best: [Free]?Int = [Free] f => (f == 0).then(0)
for d in deals:
    best = [Free] f => max(best[f], (Free.at(Int(f) - d.cores).map(g => best[g]) ?? None).map(p => p + d.cash))
print(best.values.flatten().max()!)

Accepted C++

76 lines · 8.19 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxm = 2000 * 50 + 5;

void solve() {
    int n;
    cin >> n;
    int arri[n][3];
    for (auto& [k, x, p] : arri) {
        cin >> k >> x >> p;
    }
    int m;
    cin >> m;
    int arrq[m][3];
    for (auto& [k, x, p] : arrq) {
        cin >> k >> x >> p;
    }
    vector<array<int, 3>> arr;
    for (auto& [k, x, p] : arri) {
        arr.push_back({x, k, -p});
    }
    for (auto& [k, x, p] : arrq) {
        arr.push_back({x, -k, p});
    }
    sort(begin(arr), end(arr), greater<>());
    long dp[maxm];
    fill(begin(dp), end(dp), -1e18);
    dp[0] = 0;
    for (auto& [_x, k, p] : arr) {
        long pdp[maxm];
        memcpy(pdp, dp, sizeof(dp));
        for (int i = 0; i < maxm; i++) {
            int ni = i + k;
            if (0 <= ni && ni < maxm) {
                dp[ni] = max(dp[ni], pdp[i] + p);
            }
        }
    }
    cout << *max_element(begin(dp), end(dp)) << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}