Submission #1243616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243616		edga1	Nile (IOI24_nile)	C++20	67 / 100	2091 ms	7236 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
#define ll long long
#define pb push_back
using namespace std;
struct art{
    ll w,a,b;
    bool operator<(const art &a) const{
        return a.w>w;
    }
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    int Q=E.size(),n=W.size();
    vector<art> v(n+1);
    for(int i=0; i<n; i++){
        v[i]={W[i],A[i],B[i]};
    }
    v[n]={-1,0,0};
    sort(v.begin(),v.end());
    vector<ll> r(Q);
    for(int q=0; q<Q; q++){
        int d=E[q];
        vector<ll> dp(n+1);
        dp[1]=v[1].a;
        dp[0]=0;
        for(int i=2; i<=n; i++){
            dp[i]=dp[i-1]+v[i].a;
            if(v[i].w-v[i-1].w<=d) dp[i]=min(dp[i],v[i].b+v[i-1].b+dp[i-2]);
            if(i>2){
                if(v[i].w-v[i-2].w<=d){
                    dp[i]=min(dp[i],v[i].b+v[i-2].b+v[i-1].a+dp[i-3]);
                }
            }

        }
        if(q==0){
            for(int i=1; i<=n; i++){
                //cout<<v[i].a<<' '<<v[i].b<<' '<<i<<' '<<dp[i][0]<<' '<<dp[i][1]<<'\n';
            }
        }
        r[q]=dp[n];
    }
    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