Submission #1181749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181749		sagnbaevv	Nile (IOI24_nile)	C++17	0 / 100	2096 ms	6304 KiB

nile

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

static const long long INF = 1LL<<60;

vector<int> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> D){
    int N = W.size();
    int Q = D.size();
    vector<long long> save(N);
    for(int i=0; i<N; i++){
        save[i] = A[i] - B[i];
    }

    vector<int> idx(N); 
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int p, int q){
        return W[p] < W[q];
    });

    vector<long long> Ws(N), Sv(N);
    for(int i=0; i<N; i++){
        Ws[i] = W[idx[i]];
        Sv[i] = save[idx[i]];
    }

    long long sumA = 0;
    for(int i=0; i<N; i++){
        sumA += A[i];
    }

    vector<int> result;
    for(int qi=0; qi<Q; qi++){
        long long d = D[qi];
        vector<long long> dp(N+1, 0LL); 
        long long bestVal = -INF;
        int leftPtr = 0;

        for(int k=1; k<=N; k++){
            while(Ws[k-1] - Ws[leftPtr] > d){
                leftPtr++;
            }

            bestVal = -INF;
            for(int i=leftPtr; i<k-1; i++){
                long long cand = dp[i] + Sv[i];
                if(cand > bestVal) bestVal = cand;
            }

            dp[k] = dp[k-1];
            if(bestVal != -INF){
                long long possible = bestVal + Sv[k-1];
                if(possible > dp[k]) dp[k] = possible;
            }
        }

        long long totalSaving = dp[N];
        long long cost = sumA - totalSaving;
        result.push_back((int)cost);
    }

    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