| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1324855 | 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,int l[],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=llabs(pos[x]-pos[y]);
int64 via1=llabs(pos[x]-pos[i])+c+llabs(pos[y]-pos[j]);
int64 via2=llabs(pos[x]-pos[j])+c+llabs(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;
}
