| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1324854 | xyz7577 | Shortcut (IOI16_shortcut) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using int64=long long;
int64 find_shortcut (int n,vector<int>&l,vector<int>&d, int c) {
vector<int64>pos(n);
for (int i=1;i<n;i++) pos[i]=pos[i-1]+l[i-1];
int64 ans=LLONG_MAX;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
int64 diam=0;
for (int x=0;x<n;x++) {
for (int y=x+1;y<n;y++) {
int64 normal=abs(pos[x]-pos[y]);
int64 via1=abs(pos[x]-pos[i])+c+abs(pos[y]-pos[j]);
int64 via2=abs(pos[x]-pos[j])+c+abs(pos[y]-pos[i]);
int64 best=min(normal,min(via1,via2));
int64 dist=best+d[x]+d[y];
diam=max(diam,dist);
}
}
ans=min(ans,diam);
}
}
return ans;
}
