IOI 16 shortcut

#include "shortcut.h"
#define ll long long
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
#define x first
const ll LLINF=1ll<<60;
#define y second
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vl vector<ll>
const char en='\n';

inline ll dist(const vl&pr,const vi&d,int i,int j,bool x,bool y)
{
	return pr[j]-pr[i]+x*d[i]*((i!=j)||!y)+y*d[j];
}

bool debug=0;
int ouL=1,ouR=8;

ll find_shortcut(int n,vi h,vi d,int c)
{
	if (!debug) ouL=-1;
	assert(n<=500);
	vl prs;
    prs.pb(0);
    for (int i=0;i<n-1;++i) prs.pb(prs.back()+h[i]);
    vl pr=prs;
    vl prs2;
    for (int i=0;i<n;++i) prs2.pb(prs[i]*2);
	ll ans=LLINF;
	for (int l=0;l<n;++l) for (int r=l+1;r<n;++r)
	{
		ll ma=0,ma2=d[0];
		int p=0;
		for (int i=1;i<l;++i)
		{
			ma=max(ma,dist(prs,d,p,i,1,1));
			if (-pr[i]+d[i]>ma2) ma2=-pr[i]+d[i],p=i;
		}
		int p1=p;
		ll C=-c-pr[r]+pr[l];
		int pos=l;
		queue<pair<int,ll>> q;
		deque<pair<int,ll>> s;
		int p2=l;
		ll mao=pr[p2]+d[p2];
		for (int i=l;i<=r;++i)
		{
			ll distL=dist(prs,d,i,r,1,0)+c;
			if (i!=l)
			{
				q.push({i,d[i]-pr[i]});
				while (s.size() && s.back().y<d[i]-pr[i]) s.pop_back();
				s.push_back({i,d[i]-pr[i]});
			}
			if (distL>=dist(prs,d,l,i,0,1))
			{
				if (l==ouL && r==ouR) cout<<"sve prije "<<pos<<' '<<i<<' '<<l<<' '<<r<<' '<<ma<<endl;
				ma=max(ma,dist(prs,d,p,i,1,1));
				if (l==ouL && r==ouR) cout<<"sve kasnije "<<pos<<' '<<i<<' '<<l<<' '<<r<<' '<<ma<<endl;
			}
			else
			{
				while (prs2[pos+1]<prs2[i]+C)
				{
					++pos;
					if (pr[pos]+d[pos]>mao) mao=pr[pos]+d[pos],p2=pos;
					auto m=q.front();
					q.pop();
					if (s.front()==m) s.pop_front();
				}
				if (l==ouL && r==ouR) cout<<"podjelaL "<<pos<<' '<<i<<' '<<l<<' '<<r<<' '<<ma<<' '<<distL<<' '<<p2<<' '<<s.front().x<<' '<<s.front().y<<' '<<mao<<endl;
				ma=max(ma,distL+dist(prs,d,p1,l,1,0));
				ma=max(ma,distL+dist(prs,d,l,p2,0,1));
				ma=max(ma,dist(prs,d,s.front().x,i,1,1));
				if (l==ouL && r==ouR) cout<<"nakon podjeleL "<<pos<<' '<<i<<' '<<l<<' '<<r<<' '<<ma<<' '<<distL<<' '<<p2<<' '<<s.front().x<<' '<<s.front().y<<' '<<mao<<endl;
			}
			if (-pr[i]+d[i]>ma2) ma2=-pr[i]+d[i],p=i;
		}
		int la=l;
		auto a=upper_bound(prs2.begin(),prs2.end(),prs[l]+prs[r]-c);
		int x=a-prs2.begin();
		ll ma3=-LLINF,p3=-1,ma4=-LLINF,p4=-1,ma5=-LLINF,p5=-1;
		for (int i=0;i<l;++i) if (-pr[i]+d[i]>ma3) ma3=-pr[i]+d[i],p3=i;
		for (int i=l;i<x;++i) if (pr[i]+d[i]>ma4) ma4=pr[i]+d[i],p4=i;
		for (int i=max(l,x);i<=r;++i) if (-pr[i]+d[i]>ma5) ma5=-pr[i]+d[i],p5=i;
		if (l==ouL && r==ouR) cout<<l<<' '<<r<<' '<<x<<' '<<p3<<' '<<p4<<' '<<p5<<' '<<ma<<endl;
		for (int i=r+1;i<n;++i)
		{
			ll distL=dist(prs,d,r,i,0,1)+c;
			if (p3!=-1)
			{
				ma=max(ma,min(distL+dist(prs,d,p3,l,1,0),dist(prs,d,p3,i,1,1)));
			}
			if (p4!=-1) ma=max(ma,distL+dist(prs,d,l,p4,0,1));
			if (p5!=-1) ma=max(ma,dist(prs,d,p5,i,1,1));
			if (-pr[i]+d[i]>ma5) ma5=-pr[i]+d[i],p5=i;
		}
		if (debug) cout<<l<<' '<<r<<' '<<ma<<endl;
		ans=min(ans,ma);
	}
	return ans;
}