Submission #21178

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

shortcut

#include "shortcut.h"
#include <iostream>
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;
	for(int i=0;i<n;i++)	{
		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]);
				}

			}
			ans=min(ans,f);

			// if(sums[j]-sums[i]<=c)	continue;		
			// if(f==0)	{
			// 	//first time this runs for a particular i(starting).
			// }
			// f=1;
			// cout<<i<<"  "<<j<<"  "<<ans<<endl;
		}
	}

    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