| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 57834 | robert | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
using namespace std;
vector <long long> dist[2], maxd[2]; //1 asking from the right, i.e. int the left direction, 0 asking from the left
int N;
vector<int> l, d;
int c;
int dst(int a, int b){
return dist[1][b]-dist[1][a];
}
long long find_shortcut(int n, vector<int> l_c, vector<int> d_c, int c_c){
N = n;
l = l_c;
d = d_c;
c = c_c;
dist[0].assign(N+1, 0);
maxd[0] = maxd[1] = dist[0];
dist[1] = dist[0];
dist[0][0] = dist[1][N-1] = 0;
maxd[0][0] = d[0];
maxd[1][N-1] = d[N-1];
for(int x=1; x<N; x++){
dist[0][x] = dist[0][x-1]+l[x-1];
maxd[0][x] = max(maxd[0][x-1]+l[x-1], (long long)d[x]);
}
for(int x = N-2; x>=0; x--){
dist[1][x] = dist[1][x+1]+l[x];
maxd[1][x] = max(maxd[1][x+1]+l[x], (long long)d[x]);
}
long long a = 0;
for(int x=0; x<N; x++){
a = max(a, maxd[0][x]+maxd[1][x]);
cout << dist[0][x] << " " << dist[1][x] << endl;
cout << maxd[0][x] << " " << maxd[1][x] << endl;
}
for(int x=0; x<N-1; x++){
for(int y=x+1; y<N; y++){
//count the maxdist if we put a node between x and y
long long nmxd = c+maxd[1][y]+maxd[0][x];
if(nmxd<a)
cout << x << " " << y << endl;
for(int z=x+1; z<y; z++){
nmxd = max(nmxd, (long long)min(dst(z, y), dst(x, z)+c));
nmxd = max(nmxd, (long long)min(dst(z, y)+c, dst(x, z)));
for(int z1 = z+1; z1<y; z1++){
nmxd = max(nmxd, (long long)d[z]+d[z1]+min(dst(z, z1), dst(x, z)+c+dst(z1, y)));
}
}
if(nmxd<a)
cout << x << " " << y << " " << nmxd << endl;
a = min(a, nmxd);
}
}
return a;
}
int main(){
vector<int> l = {10, 20, 20}, d = {0, 40, 0, 30};
cout << find_shortcut(4, l, d, 10) << endl;
}