Submission #1241646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241646		nibert	Nile (IOI24_nile)	C++20	0 / 100	1058 ms	1744900 KiB

nile

#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
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<long long> result(Q);

    // Build the weight difference matrix
    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, numeric_limits<long long>::max()));

    // Sort indices for stable results
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);

    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return A[i] - B[i] > A[j] - B[j]; // prioritize sending alone if (A[i] - B[i]) is large
    });

    vector<bool> used(N, false);
    long long best = 0;
    int i = N - 1;
    while (i > 0) {
        int a = idx[i];
        int b = idx[i - 1];
        best += B[a] + B[b];
        used[a] = used[b] = true;
        i -= 2;
    }
    if (i == 0) {
        best += A[idx[0]];
    }

    // Set answer for all Q
    for (int j = 0; j < Q; ++j) {
        result[j] = best;
    }
    return result;
}

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