| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 547037 | fvogel499 | Shortcut (IOI16_shortcut) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
* File created on 04/09/2022 at 10:34:35.
* Link to problem:
* Description:
* Time complexity: O()
* Space complexity: O()
* Status: ---
* Copyright: Ⓒ 2022 Francois Vogel
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;
#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear
#define int ll
#define ll long long
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e18;
int find_shortcut_act(int n, vi dist, vi at, int extraPath) {
int prefD [n];
prefD[0] = 0;
for (int i = 1; i < n; i++) prefD[i] = prefD[i-1]+dist[i-1];
int lft [n];
lft[0] = at[0];
for (int i = 1; i < n; i++) lft[i] = max(lft[i-1]+dist[i-1], at[i]);
int rgt [n];
rgt[n-1] = at[n-1];
for (int i = n-2; i >= 0; i--) rgt[i] = max(rgt[i+1]+dist[i], at[i]);
int res = inf;
for (int _ = (1LL<<60); _; _ /= 2) {
int prop = res-_;
if (prop < 0) continue;
bool poss = false;
for (int i = 0; i < n; i++) {
if (lft[i] > prop) break;
int till = n;
while (till-1 > i && rgt[till-1]+lft[i]+min(extraPath, prefD[till-1]-prefD[i]) <= prop) till--;
if (till == n) break;
if (till <= i+1) {
poss = true;
break;
}
int len = till-i-1;
assert(len >= 1);
int toNext [len];
for (int j = i+1; j < till-1; j++) toNext[j-i-1] = dist[j-1];
toNext[len-1] = dist[i]+dist[till-1]+extraPath;
int prefNext [len];
prefNext[0] = toNext[0];
for (int i = 1; i < len; i++) prefNext[i] = prefNext[i-1]+toNext[i];
int locAt [len];
for (int j = 0; j < len; j++) locAt[j] = at[i+j+1];
bool ok = true;
int k = 0;
int mx = 0, sum = 0;
for (int j = 0; j < len; j++) {
if (j) {
mx -= toNext[j-1];
sum -= toNext[j-1];
}
while (sum+toNext[k] <= prefNext[len-1]/2LL) {
sum += toNext[k];
k++;
k %= len;
mx = max(mx, sum+at[k]);
}
if (mx+at[j] > prop) {
ok = false;
break;
}
if (at[j]+prefD[j]-prefD[i]+lft[i] > prop || at[j]+prefD[till]-prefD[j]+rgt[till] > prop) {
ok = false;
break;
}
}
if (ok) {
poss = true;
break;
}
}
if (poss) {
res = prop;
}
}
return res;
}
int find_shortcut(int n, vector<signed> iL, vector<signed> iD, int c) {
vi toL, toD;
for (int i : iL) toL.pb(i);
for (int i : iD) toD.pb(i);
return find_shortcut_act(n, toL, toD, c);
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, c;
cin >> n >> c;
vector<signed> Il(n-1), Id(n);
for (int i = 0; i < n-1; i++) cin >> Il[i];
for (int i = 0; i < n; i++) cin >> Id[i];
cout << find_shortcut(n, Il, Id, c);
cout.flush();
int d = 0;
d++;
}