Submission #1304462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304462		TroySer	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	18424 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 9e18;

struct Artifact {
    ll w;
    ll a;
    ll b;
};

const ll MAX_SZ = 1e5 + 10;
ll memo[MAX_SZ];

ll dp(ll D, vector<Artifact> &artifacts) {

    memset(memo, -1LL, sizeof(memo));

    ll N = (ll)artifacts.size();
    memo[N] = 0;

    ll dPointer = N - 1;

    set<pair<ll, ll> > res2Selection;
    map<ll, pair<ll, ll> > toRemove;

    ll accumInd = N;
    ll accum = 0;

    for (ll ind = N - 1; ind >= 0; ind--) {

        if (ind < N - 1) accum += artifacts[ind].a;
        // cout << "accum(" << ind << "): " << accum << endl;

        // res1: keep single
        ll res1 = memo[ind + 1] + artifacts[ind].a;

        // remove stuff you cannot pair-up
        while (artifacts[dPointer].w - artifacts[ind].w > D) {
            res2Selection.erase(toRemove[dPointer]);
            dPointer--;
        }

        // cout << "currentInd (" << ind << "): ";
        // for (auto l: res2Selection) {
        //     cout << l.first << ", " << l.second << "; ";
        // }
        // cout << endl;
        // cout << "----" << endl;

        if (res2Selection.size() == 0) { // nothing to pair-up

            res2Selection.insert({memo[ind + 1] + artifacts[ind].b - accum, ind});
            toRemove[ind] = {memo[ind + 1] + artifacts[ind].b - accum, ind};

            memo[ind] = res1;
            continue;

        }

        // res2: pair-up with best DP
        pair<ll, ll> bestPair = *res2Selection.begin();
        ll res2 = artifacts[ind].b + bestPair.first + accum - artifacts[ind].a;

        res2Selection.insert({memo[ind + 1] + artifacts[ind].b - accum, ind});
        toRemove[ind] = {memo[ind + 1] + artifacts[ind].b - accum, ind};

        memo[ind] = min(res1, res2);

    }

    // for (ll i = 0; i <= N; i++) {
    //     cout << memo[i] << ", ";
    // }
    // cout << endl;

    return memo[0];

}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {

    ll Q = (ll)E.size();
    ll N = (ll)A.size();

    vector<ll> R(Q);
    
    vector<Artifact> artifacts;
    artifacts.reserve(N);
    for (ll i = 0; i < N; i++) {
        artifacts.push_back(Artifact{W[i], A[i], B[i]});
    }

    sort(artifacts.begin(), artifacts.end(), [&](Artifact &a, Artifact &b) {
        if (a.w == b.w) {
            if (a.a == b.a) {
                return a.b < b.b;
            }
            return a.a < b.a;
        }
        return a.w < b.w;
    });
    
    for (ll queryInd = 0; queryInd < Q; queryInd++) {

        ll res = dp(E[queryInd], artifacts);
        R[queryInd] = res;

    }

    return R;

}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18