Submission #1304364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304364		TroySer	Nile (IOI24_nile)	C++20	17 / 100	2097 ms	15228 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 ind, ll D, vector<Artifact> &artifacts) {

    ll N = (ll)artifacts.size();
    
    if (ind == N) return 0;
    if (memo[ind] != -1LL) {
        return memo[ind];
    }

    // Keep this artifact isolated
    ll res1 = dp(ind + 1, D, artifacts) + artifacts[ind].a;

    // Pair this artifact with another
    ll res2 = INF;
    ll notIncluded = 0;

    for (ll newInd = ind + 1; (newInd < N) && (artifacts[newInd].w - artifacts[ind].w <= D); newInd++) {

        res2 = min( // pair this artifact with a later artifact
            res2, 
            dp(newInd + 1, D, artifacts) + artifacts[ind].b + artifacts[newInd].b + notIncluded
        );
        notIncluded += artifacts[newInd].a; // keep this artifact single

    }

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

}

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++) {

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

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

    }

    return R;

}

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