Submission #1220735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220735		cjoa	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	15288 KiB

nile

#include "nile.h"

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Artifact {
    int weight;
    int cost;
};

vector<Artifact> artifacts;

vector<bool> cached;
vector<long long> memo;
long long dp(const int max_allowed_weight_dif, int i) {
    if (i < 0)
        return 0;

    long long& res = memo[i];
    if (!cached[i]) {
        // ship artifact[i] by itself
        res = artifacts[i].cost + dp(max_allowed_weight_dif, i-1);

        // match with artifact[i-1]
        if (i >= 1 and artifacts[i].weight - artifacts[i-1].weight <= max_allowed_weight_dif) {
            res = min(res, dp(max_allowed_weight_dif, i-2));
        }

        // match with artifact[i-2] and ship artifact[i-1] by itself
        if (i >= 2 and artifacts[i].weight - artifacts[i-2].weight <= max_allowed_weight_dif) {
            res = min(res, artifacts[i-1].cost + dp(max_allowed_weight_dif, i-3));
        }

        cached[i] = true;
    }
    return res;
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B,
                                  vector<int> E) {
    // subtask 5: Q <= 5

    const int N = W.size();
    if (N == 1)
        return vector<long long>(N, A[0]);

    long long base_cost = 0;
    for (int i = 0; i < N; i++)
        base_cost += B[i];

//  cerr << "base_cost: " << base_cost << endl;

    const int Q = E.size();
    vector<long long> R(Q, base_cost);

    artifacts.clear();
    for (int i = 0; i < N; i++)
        artifacts.push_back({W[i], A[i] - B[i]});

    sort(artifacts.begin(), artifacts.end(),
         [&] (Artifact a, Artifact b) -> bool {return a.weight < b.weight; });

    for (int j = 0; j < Q; j++) {
        int e = E[j];
        cached.assign(N, false);
        memo.assign(N, -1);
        R[j] += dp(e, N-1);
    }

    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