Submission #21179

#	Time	Username	Problem	Language	Result	Execution time	Memory
21179		sbansalcs	Shortcut (IOI16_shortcut)	C++14	31 / 100	2000 ms	41084 KiB

shortcut

#include "shortcut.h"
#include <iostream>
#include <assert.h>
const int N = 1e6+2;
typedef long long ll;
using namespace std;
ll dp1[N],dp2[N];
ll dp3[N],dp4[N];
ll sums[N];
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{	
	for(int i=0;i<n;i++)	{
		if(i==0)	dp1[i]=d[i];
		else	dp1[i]=max((ll)d[i],dp1[i-1]+l[i-1]);
	}
	for(int i=n-1;i>=0;i--)	{
		if(i==n-1)	dp2[i]=d[i];
		else	dp2[i]=max((ll)d[i],dp2[i+1]+l[i]);
	}
	for(int i=0;i<n;i++)	{
		if(i==0)	dp3[i]=d[i];
		else	dp3[i]=max(dp3[i-1],d[i]+l[i-1]+dp1[i-1]);	
	}
	for(int i=n-1;i>=0;i--)	{
		if(i==n-1)	dp4[i]=d[i];
		else	dp4[i]=max(dp4[i+1],l[i]+dp2[i+1]+d[i]);
	}
	for(int i=1;i<n;i++)	{
		sums[i]=l[i-1]+sums[i-1];
	}
	// for(int i=0;i<n;i++)	{
	// 	cout<<i<<" : "<<dp3[i]<<" , "<<dp4[i]<<endl;
	// }
	ll ans=dp3[n-1];
	ll lx;
	ll prev=0;bool Gf=0,Gf2=0;
	for(int i=0;i<n;i++)	{
		prev=0,Gf=0,Gf2=0;
		for(int j=i+1;j<n;j++)	{

			lx=sums[j]-sums[i];
			if(lx<=c)	continue;

			ll f=max(dp3[i],max(dp4[j],c+dp1[i]+dp2[j]));
			for(int x=i+1;x<j;x++)	{
				ll _x=sums[x]-sums[i];
				f=max(f,min(_x,lx-_x+c)+dp1[i]+d[x]);
				f=max(f,min(lx-_x,_x+c)+dp2[j]+d[x]);
				for(int y=x+1;y<j;y++)	{
					ll f2=sums[y]-sums[x];
					f=max(f,min(f2,lx+c-f2)+d[x]+d[y]);
				}

			}
			if(Gf==0)	{
				Gf=1;
				prev=f;
			}
			else {
				if(Gf2==0)	{
					if(f>prev)	{
						Gf2=1;
					}

				}
				else	{
					assert(f>=prev);
				}	
			}
			// cout<<i<<" , "<<j<<"  :  "<<f<<endl;
			ans=min(ans,f);
		}
	}

    return ans;
}

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