Submission #1210698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210698		Aviansh	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	12104 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    long long n = A.size();
    vector<array<long long,3>>boxes(n);
    for(long long i = 0;i<n;i++){
        boxes[i]={W[i],A[i],B[i]};
    }
    sort(boxes.begin(),boxes.end());
    long long q = (long long)E.size();
    vector<long long>ans(q);
    long long prefa[n];
    prefa[0]=boxes[0][1];
    for(long long i = 1;i<n;i++){
        prefa[i]=prefa[i-1]+boxes[i][1];
    }
    for(long long z = 0;z<q;z++){
        long long d = E[z];
        long long dp[n];
        dp[0]=boxes[0][1];
        multiset<long long>vals;
        long long x = 0;
        vals.insert(1LL*boxes[0][2]-prefa[0]);
        long long valarr[n];
        valarr[0]=1LL*boxes[0][2]-prefa[0];
        for(long long i = 1;i<n;i++){
            dp[i]=dp[i-1]+boxes[i][1];

            while(boxes[x][0]<boxes[i][0]-d){
                vals.erase(vals.find(valarr[x]));
                x++;
            }

            if(vals.size())
                dp[i]=min(dp[i],1LL*boxes[i][2]+prefa[i-1]+(*vals.begin()));
            vals.insert(dp[i-1]+1LL*boxes[i][2]-prefa[i]);
            valarr[i]=dp[i-1]+1LL*boxes[i][2]-prefa[i];
        }
        ans[z]=dp[n-1];
    }
    return ans;
}

• 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