| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314136 | activedeltorre | Shortcut (IOI16_shortcut) | C++20 | 0 ms | 0 KiB |
include "shortcut.h"
long long spar[100005];
using namespace std;
#include <vector>
int inf=1e17;
long long dist(int a,int b,int c,int d,int add)
{
long long minim=inf;
minim=min(minim,spar[b]-spar[a]);
minim=min(minim,abs(spar[b]-spar[d])+abs(spar[a]-spar[c])+add);
return minim;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
for(int i=2; i<=n; i++)
{
spar[i]=spar[i-1]+l[i-2];
}
long long best=inf;
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
long long worst=0;
if(c<spar[j]-spar[i])
{
for(int z=1; z<=n; z++)
{
for(int z2=z+1; z2<=n; z2++)
{
worst=max(worst,dist(z,z2,i,j,c)+d[z-1]+d[z2-1]);
}
}
best=min(best,worst);
}
}
}
return best;
}
