Submission #69398

#	Time	Username	Problem	Language	Result	Execution time	Memory
69398		hamzqq9	Shortcut (IOI16_shortcut)	C++14	0 / 100	2 ms	528 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 200000000000000000
#define MOD 1000000007
#define N 3005
#define MAX 10000006
#define LOG 30
#define KOK 200
using namespace std;

int l[N],d[N],n,c;
int ar[2*N];
ll ans;
ll pre[N],suf[N],mx_L[N],mx_R[N],sum[N],psum[2*N];

ll fmax(int bas,int son) {

	ll res=max(pre[bas],suf[son]);

	umax(res,min(1ll*c,sum[son]-sum[bas])+mx_L[bas]+mx_R[son]+sum[bas]-sum[son]);

	int range=son-bas+1;

	if(range>1) {

		for(int i=bas;i<=son;i++) {

			ar[i-bas+1]=ar[i+range-bas+1]=i;

		}
		
		for(int i=2;i<=range*2;i++) {

			if(i!=range+1) psum[i]=psum[i-1]+l[ar[i-1]];
			else psum[i]=psum[i-1]+c;

		}
		
		ll asum=psum[range+1];
		
		for(int i=bas+1;i<=son;i++) {

			if(sum[i]-sum[bas]>c+sum[son]-sum[i]) {

				umax(res,mx_L[bas]+d[i]+c+sum[son]-sum[i]+sum[bas]);			

			}
			else {

				umax(res,mx_L[bas]+d[i]+sum[i]);

			}

		}

		for(int i=bas;i<son;i++) {

			if(sum[son]-sum[i]>c+sum[i]-sum[bas]) {

				umax(res,mx_R[son]+d[i]+c+sum[i]-sum[bas]-sum[son]);

			}
			else {

				umax(res,mx_R[son]+d[i]-sum[i]);

			}

		}

		int ptr=0;

		deque<ll> deq;

		for(int i=1;i<=range;i++) {

			while(ptr+1<=2*range && psum[ptr+1]-psum[i]<=asum-(psum[ptr+1]-psum[i])) {

				ptr++;

				while(!deq.empty() && deq.back()<psum[ptr]+d[ar[ptr]]) deq.pop_back();

				deq.pb(psum[ptr]+d[ar[ptr]]);

			}

			if(!deq.empty()) {

				umax(res,deq.front()-psum[i]+d[ar[i]]);

				if(deq.front()==psum[i]+d[ar[i]]) deq.pop_front();

			}

		}

	}

	return res;

}

void build() {

	for(int i=1;i<n;i++) sum[i]=sum[i-1]+l[i-1];

	for(int i=0;i<n;i++) mx_L[i]=mx_R[i]=-inf;

	for(int i=0;i<n;i++) {

		pre[i]=max((i-1>=0?pre[i-1]:0),(i-1>=0?mx_L[i-1]:-sum[i])+d[i]+sum[i]);

		mx_L[i]=max((i-1>=0?mx_L[i-1]:-inf),d[i]-sum[i]);

	}

	for(int i=n-1;i>=0;i--) {

		suf[i]=max((i+1<n?suf[i+1]:0),(i+1<n?mx_R[i+1]:sum[i])+d[i]-sum[i]);

		mx_R[i]=max((i+1<n?mx_R[i+1]:-inf),d[i]+sum[i]);

	}

}

void solve(int bas,int son,int pbas,int pson) {

	if(bas>son) return ;

	int opt=pbas;
	ll res=inf;

	umax(pbas,orta);
	umax(pson,orta);

	for(int i=pbas;i<=pson;i++) {

		ll mx=fmax(orta,i);

		if(res>mx) {

			res=mx;
			opt=i;

		}

	}

	umin(ans,res);

	//printf("%d %d %lld\n",orta,opt,res);

	solve(bas,orta-1,pbas,opt);
	solve(orta+1,son,opt,pson);

}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {

	::n=n;
	::c=c;

	for(int i=0;i<n;i++) ::l[i]=l[i],::d[i]=d[i];

	ans=inf;

	build();

	//printf("TRY-->%lld\n",fmax(2,7));

	for(int i=0;i<n;i++) for(int j=i;j<n;j++) umin(ans,fmax(i,j));

	//solve(0,n-1,0,n-1);

	return ans;

}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3