Submission #1317565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317565		foxserg	Nile (IOI24_nile)	C++20	67 / 100	2091 ms	4900 KiB

nile

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) {
    int n = A.size();

    int p[n];
    iota(p, p + n, 0);

    sort(p, p + n, [&](int i, int j) {
        return W[i] < W[j];
    });

    vector <int> nW(n);
    vector <int> nA(n);
    vector <int> nB(n);
    for (int i = 0; i < n; ++i) {
        nW[i] = W[p[i]];
        nA[i] = A[p[i]];
        nB[i] = B[p[i]];
    }

    W = move(nW);
    A = move(nA);
    B = move(nB);

    vector <ll> R;
    R.reserve(E.size());

    ll sm = 0;
    for (int i = 0; i < n; ++i) sm += B[i];
    for (int i = 0; i < n; ++i) A[i] -= B[i];

    for (int D : E) {
        ll dp[n + 1];

        dp[0] = 0;
        dp[1] = A[0];
        if (W[1] - W[0] <= D) {
            dp[2] = 0;
        } else {
            dp[2] = A[0] + A[1];
        }

        for (int i = 2; i < n; ++i) {
            dp[i + 1] = dp[i] + A[i];

            if (W[i] - W[i - 1] > D) continue;

            dp[i + 1] = min(dp[i + 1], dp[i - 1]);
            if (W[i] - W[i - 2] > D) continue;

            dp[i + 1] = min(dp[i + 1], dp[i - 2] + A[i - 1]);
        }

        R.push_back(dp[n] + sm);
    }

    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