| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 140484 | bazsi700 | Roller Coaster Railroad (IOI16_railroad) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
#define hashA 1257958787
#define hashB 1539500609
#define endl "\n"
ll pref[10005];
ll getdist(ll a, ll b) {
if(a > b) {
swap(a,b);
}
return pref[b]-pref[a];
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
ll ans = 0;
ll currdist = d[0];
for(int i = 1; i < n; i++) {
pref[i] = pref[i-1]+l[i-1];
}/*
for(int i = 1; i < n; i++) {
currdist+= l[i-1];
ans = max(ans,currdist+d[i]);
currdist = max(currdist,(ll)d[i]);
}*/
ll mn = INF;
for(int b1 = 0; b1 < n; b1++) {
for(int b2 = b1+1; b2 < n; b2++) {
ll mx = 0;
ll worstnormal = d[0];
ll worstshort = d[0]+getdist(0,b1);
for(int v = 1; v < n; v++) {
worstnormal+= l[v-1];
ll dist = worstnormal+d[v];
dist = min(dist,worstshort+c+getdist(v,b2)+d[v]);
worstshort = max(worstshort,getdist(v,b1)+d[v]);
worstnormal = max(worstnormal,(ll)d[v]);
mx = max(mx,dist);
}
mn = min(mn,mx);
}
}
return mn;
}