Submission #889208

#	Time	Username	Problem	Language	Result	Execution time	Memory
889208		Faisal_Saqib	Shortcut (IOI16_shortcut)	C++17	38 / 100	736 ms	32340 KiB

shortcut

#pragma once
#include <vector>
#include <set>
#include <iostream>
using namespace std;
long long pre[1000];
long long mxp[1000][1000];
long long mip[1000][1000];
long long dist(int&i,int&j)
{
	return abs(pre[j]-pre[i]);
}
long long find_shortcut(int n,vector<int> l,vector <int> d, int c)
{
	for(int i=1;i<n;i++)
		pre[i]=pre[i-1]+l[i-1];
	for(int i=0;i<n;i++)
	{
		mxp[i][i]=pre[i]+d[i];
		mip[i][i]=pre[i]-d[i];
		for(int j=i+1;j<n;j++)
		{
			mxp[i][j]=max(mxp[i][j-1],pre[j]+d[j]);
			mip[i][j]=min(mip[i][j-1],pre[j]-d[j]);
		}
	}
	long long ans=1e18;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			long long cur=0;
			int bl=-1;
			int br=n;
			for(int i1=0;i1<n;i1++)
			{
				br=n;
				while(bl+1<br)
				{
					int mid=(br+bl)/2;
					if(dist(i1,mid)<=(c+dist(i1,i)+dist(j,mid)))
					{
						bl=mid;
					}
					else
					{
						br=mid;
					}
				}
				if(i1+1 <= bl)
				{
					cur=max(cur,mxp[i1+1][bl]-pre[i1]+d[i1]);
				}
				if(bl+1 < n)
				{
					if((bl+1)<=j)
					{
						cur=max(cur,c+d[i1]+dist(i1,i)+pre[j]-mip[bl+1][j]);
					}
					if((j+1)<n)
					{
						cur=max(cur,c+d[i1]+dist(i1,i)+mxp[j+1][n-1]-pre[j]);
					}
				}
			}
			ans=min(ans,cur);
		}
	}
	return ans;
}

Compilation message (stderr)

shortcut.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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