| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 831604 | OrazB | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
#define ll long long
const int N = 1e5+5;
ll pref[N], suff[N], p[N];
ll dis(int l, int r, vector<int> d){
if (l > r) swap(l, r);
if (l == r) return d[l];
ll x = p[r-1]+d[l]+d[r];
if (l) x -= p[l-1];
return x;
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
for (int i = 0; i < n; i++){
ll sum = 0;
pref[i] = suff[i] = d[i];
for (int j = i-1; j >= 0; j--){
sum += l[j];
pref[i] = max(pref[i], sum+d[j]);
}
sum = l[i];
for (int j = i+1; j < n; j++){
suff[i] = max(suff[i], sum+d[j]);
if (j == n-1) break;
sum += l[j];
}
}
for (int i = 0; i < n-1; i++){
p[i] = l[i];
if (i) p[i] += p[i-1];
}
// cout << dis(0, 5, d) << '\n';
ll mn = 1e18;
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
ll mx = pref[i]+suff[j]+c;
for (int x = 0; x < n; x++){
for (int k = i; k <= j; k++){
ll minn = dis(x, k, d);
// if (x == 0 and k == 5 and i == 3 and j == 4) cout << minn << '\n';
if (x < k) minn = min(minn, dis(x, i, d)+c+dis(k, j, d));
else minn = min(minn, dis(x, j, d)+c+dis(i, k, d));
mx = max(mx, minn);
}
}
mn = min(mn, mx);
// if (mn == 80) cout << i << " " << j << '\n';
}
}
return mn;
}
int main()
{
int n, c;
assert(2 == scanf("%d%d", &n, &c));
std::vector<int> l(n - 1);
std::vector<int> d(n);
for (int i = 0; i < n - 1; i++)
assert(1 == scanf("%d", &l[i]));
for (int i = 0; i < n; i++)
assert(1 == scanf("%d", &d[i]));
long long t = find_shortcut(n, l, d, c);
printf("%lld\n", t);
return 0;
}