Submission #1312225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312225		exoworldgd	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	13068 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define ll long long
using namespace std;
const ll INF=1e18;
vector<ll>calculate_costs(vector<int>W,vector<int>A,vector<int>B,vector<int>E){
	int n=W.size(),q=E.size();
	vector<int>ord(n),w(n),a(n),b(n);
	iota(ord.begin(),ord.end(),0),sort(ord.begin(),ord.end(),[&](int i,int j){return W[i]<W[j];});
	for(int i=0;i<n;i++)w[i]=W[ord[i]],a[i]=A[ord[i]],b[i]=B[ord[i]];
	auto solve=[&](int d){
		vector<vector<ll>>dp(n+1,vector<ll>(4,INF));
		dp[n][0]=0;
		for(int i=n-1;i>=0;i--){
			dp[i][0]=min(a[i]+dp[i+1][0],b[i]+dp[i+1][1]);
			for(int j=i-1;j+1&&i-j<=2&&w[i]-w[j]<=d;j--)dp[i][i-j]=min(a[i]+dp[i+1][i+1-j],b[i]+dp[i+1][0]);
		}
		return dp[0][0];
	};
	vector<ll>R(q);
	for(int i=0;i<q;i++)R[i]=solve(E[i]);
	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