Submission #1306843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306843		michael12	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	4656 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
using namespace std;

vector<long long> calculate_costs(
    vector<int> W,
    vector<int> A,
    vector<int> B,
    vector<int> E
) {
    int N = W.size();
    int Q = E.size();

    vector<array<int,3>> at(N);
    for (int i = 0; i < N; i++) {
        at[i] = {W[i], A[i], B[i]};
    }

    sort(at.begin(), at.end());

    long long sm = 0;
    for (int i = 0; i < N; i++) {
        sm += at[i][1];
    }

    vector<long long> rs(Q);

    for (int qi = 0; qi < Q; qi++) {
        int D = E[qi];
        vector<long long> dp(N, 0);

        for (int i = 0; i < N; i++) {
            if (i > 0) dp[i] = dp[i - 1];

            for (int j = i - 1; j >= 0; j--) {
                if (at[i][0] - at[j][0] > D) break;

                long long sv =
                    (long long)at[i][1] + at[j][1]
                    - at[i][2] - at[j][2];

                if (j > 0)
                    dp[i] = max(dp[i], dp[j - 1] + sv);
                else
                    dp[i] = max(dp[i], sv);
            }
        }

        rs[qi] = sm - dp[N - 1];
    }

    return rs;
}

• 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