Submission #1102254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102254		ezzzay	Nile (IOI24_nile)	C++17	67 / 100	2068 ms	11160 KiB

nile

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {                                   	
    int q = (int)E.size();
    int n = W.size();
    vector<ll>ans;
    vector<pair<ll,ll> >v;
    for(int i=0;i<n;i++){
    	v.pb({W[i],i});
	}
	sort(v.begin(),v.end());
	
	for(int f=0;f<q;f++){
		ll d=E[f];
		vector<vector<ll> > dp ( n+5 , vector<ll> (2)); 
		for(int i=1;i<=n;i++){
			dp[i][0]=1e17;
			dp[i][1]=1e17;
		}
		for(int i=0;i<n;i++){
			int a,b,c;
			a=v[i].ss;
			if(i>0)b=v[i-1].ss;
			if(i>1)c=v[i-2].ss;
			if(i>0) {
				if(abs(W[a]-W[b])<=d) dp[i+1][1]=min(dp[i+1][1],dp[i][0]-A[b]+B[b]+B[a]);
			}
			if(i>1) {
				if(abs(W[a]-W[c])<=d) dp[i+1][1]=min(dp[i+1][1],dp[i-1][0]-A[c]+B[c]+B[a]+A[b]);
			}
			dp[i+1][0]=min(dp[i+1][0],min(dp[i][1],dp[i][0])+A[a]);
		}
		ans.pb(min(dp[n][0],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