Submission #1178191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178191		alexander707070	Nile (IOI24_nile)	C++20	0 / 100	37 ms	7352 KiB

nile

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long inf=1e17;

struct item{
	int w;
	int a,b;

	inline friend bool operator < (item fr,item sc){
		return fr.w<sc.w;
	}
};

int delta;
int n;
item a[MAXN];
vector< pair<int,int> > raz,qs;
long long ans[MAXN],dp[MAXN];

long long slow(int l,int r){
	dp[l-1]=0;

	for(int i=l;i<=r;i++){
		dp[i]=dp[i-1]+a[i].a;
		if(i-1>=l and (a[i].w-a[i-1].w)<=delta)dp[i]=min(dp[i],dp[i-2]+a[i].b+a[i-1].b);
		if(i-2>=l and (a[i].w-a[i-2].w)<=delta)dp[i]=min(dp[i],dp[i-3]+a[i-2].b+a[i-1].a+a[i].b);
	}

	return dp[r];
}

struct node{
	long long ans[3][3];
};

node tree[4*MAXN];

void solve(int v,int l,int r){
	if(r-l+1<=7){
		long long pref=0;
		for(int i=0;i<3;i++){
			long long suff=0;
			
			for(int f=0;f<3;f++){
				tree[v].ans[i][f]=slow(l+i,r-f)+pref+suff;
				suff+=a[r-f].a;
			}

			pref+=a[l+i].a;
		}

		return;
	}

	int mid=(l+r)/2;
	solve(2*v,l,mid);
	solve(2*v+1,mid+1,r);

	auto s=tree[2*v],t=tree[2*v+1];

	for(int i=0;i<3;i++){
		for(int f=0;f<3;f++){
			long long curr=s.ans[i][0]+t.ans[0][f];

			if(abs(a[mid].w-a[mid+1].w)<=delta)curr=min(curr,s.ans[i][1]+t.ans[1][f]-a[mid].a-a[mid+1].a+a[mid].b+a[mid+1].b);
			if(abs(a[mid].w-a[mid+2].w)<=delta)curr=min(curr,s.ans[i][1]+t.ans[2][f]-a[mid].a-a[mid+2].a+a[mid].b+a[mid+2].b);
			if(abs(a[mid-1].w-a[mid+1].w)<=delta)curr=min(curr,s.ans[i][2]+t.ans[1][f]-a[mid-1].a-a[mid+1].a+a[mid-1].b+a[mid+1].b);
		}
	}
}

vector<long long> calculate_costs(vector<int> W, vector<int> A,vector<int> B,vector<int> E){
	n=int(W.size());

	for(int i=1;i<=n;i++){
		a[i]={W[i-1],A[i-1],B[i-1]};
	}
	sort(a+1,a+n+1);

	delta=0;
	for(int i=1;i<=n;i++){
		if(i+1<=n)raz.push_back({a[i+1].w-a[i].w,i});
		if(i+2<=n)raz.push_back({a[i+2].w-a[i].w,i});
	}

	sort(raz.begin(),raz.end());

	for(int i=0;i<E.size();i++){
		qs.push_back({E[i],i});
	}

	sort(qs.begin(),qs.end());

	int pt=0;
	for(int i=0;i<qs.size();i++){
		delta=qs[i].first;

		/*while(pt<raz.size() and raz[pt].first<=qs[i].first){
			tree.upd(raz[pt].second);
			pt++;
		}*/

		solve(1,1,n);
		ans[qs[i].second]=tree[1].ans[0][0];
	}

	vector<long long> sol;
	for(int i=0;i<qs.size();i++)sol.push_back(ans[i]);

	return sol;
}

/*int main(){

	auto res=calculate_costs({15, 12, 2, 10, 21},
		{5, 4, 5, 6, 3},
		{1, 2, 2, 3, 2},
		{5, 9, 1});

	for(auto s:res)cout<<s<<" ";

	return 0;
}*/

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