Submission #1243590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243590		edga1	Nile (IOI24_nile)	C++20	17 / 100	2094 ms	10988 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
#define ll long long
#define pb push_back
using namespace std;
struct art{
    int 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<vector<ll>> dp(n+1,vector<ll>(2,1e18));
        dp[1][0]=v[1].a;
        dp[0][0]=dp[0][1]=0;
        for(int i=2; i<=n; i++){
            dp[i][0]=min(dp[i-1][0],dp[i-1][1])+v[i].a;
            if(v[i].w-v[i-1].w<=d) dp[i][1]=min(dp[i][1],v[i].b+v[i-1].b+min(dp[i-2][0],dp[i-2][1]));
            if(i>2){
                if(v[i].w-v[i-2].w<=d){
                    dp[i][1]=min(dp[i][1],v[i].b+v[i-2].b+v[i-1].a+min(dp[i-3][0],dp[i-3][1]));
                }
            }

        }
        r[q]=min(dp[n][0],dp[n][1]);
    }
    return r;
}

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