제출 #547040

#제출 시각아이디문제언어결과실행 시간메모리
547040fvogel499Shortcut (IOI16_shortcut)C++17
0 / 100
0 ms304 KiB
/* * 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+locAt[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(signed n, vector<signed> iL, vector<signed> iD, signed 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++; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...