Submission #1238882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238882		MarwenElarbi	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	6216 KiB

nile

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 1e5+5;
long long dp[nax];
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
    int n=A.size();
    int q=E.size();
    vector<pair<int,pair<int,int>>> tab(n);
    vector<long long> answer(q);
    for (int i = 0; i < n; ++i) tab[i]={W[i],{A[i],B[i]}};
    sort(tab.begin(),tab.end());
    for (int i = 0; i < n; ++i)
    {
        W[i]=tab[i].fi;
        A[i]=tab[i].se.fi;
        B[i]=tab[i].se.se;
    }
    for (int k = 0; k < q; ++k)
    {
        int d = E[k];
        memset(dp,0,sizeof dp);
        for (int i = 0; i < n; ++i)
        {
            dp[i]=1e18;
            long long cur=0;
            int mn=1e9;
            for (int j = i; j > i-4; --j)
            {
                if(j<0) break;
                if(W[i]-W[j]>d) break;
                cur+=B[j];
                mn=min(mn,A[j]-B[j]);
                if((i-j+1)%2) dp[i]=min(dp[i],cur+mn+(j ? dp[j-1] : 0));
                else dp[i]=min(dp[i],cur+(j ? dp[j-1] : 0));
            }
        }
        answer[k]=dp[n-1];
    }
    return answer;
}

• 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