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