Submission #388584

#TimeUsernameProblemLanguageResultExecution timeMemory
388584KeshiShortcut (IOI16_shortcut)C++17
38 / 100
339 ms210884 KiB
//In the name of God #include <bits/stdc++.h> #include "shortcut.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll maxn = 2100; const ll mod = 1e9 + 7; const ll inf = 1e18; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() #define lc (id << 1) #define rc (lc | 1) struct node{ ll mxr, mxl, mx; node(){ mxr = mxl = mx = -inf; } }; ll n, ps[maxn], d[maxn]; node seg[maxn << 2]; node dp[maxn][maxn]; node mrg(node l, node r){ if(l.mx == -inf) return r; if(r.mx == -inf) return l; node nd; nd.mx = max({l.mx, r.mx, l.mxl + r.mxr}); nd.mxl = max(l.mxl, r.mxl); nd.mxr = max(l.mxr, r.mxr); return nd; } void bld(ll id, ll s, ll e){ if(e - s == 1){ seg[id].mx = d[s]; seg[id].mxl = d[s] - ps[s]; seg[id].mxr = d[s] + ps[s]; return; } ll mid = (s + e) >> 1; bld(lc, s, mid); bld(rc, mid, e); seg[id] = mrg(seg[lc], seg[rc]); return; } node get(ll id, ll s, ll e, ll l, ll r){ if(r <= s || e <= l) return node(); if(l <= s && e <= r) return seg[id]; ll mid = (s + e) >> 1; return mrg(get(lc, s, mid, l, r), get(rc, mid, e, l, r)); } void pre(){ for(ll i = 0; i <= n; i++){ for(ll j = i; j <= n; j++){ dp[i][j] = get(1, 0, n, i, j); } } } node get(ll l, ll r){ /*node nd; nd.mx = d[l]; nd.mxl = d[l] - ps[l]; nd.mxr = d[l] + ps[l]; for(ll i = l + 1; i < r; i++){ nd.mx = max(nd.mx, nd.mxl + d[i] + ps[i]); nd.mxl = max(nd.mxl, d[i] - ps[i]); nd.mxr = max(nd.mxr, d[i] + ps[i]); } return nd;*/ //if(dp[l][r].mx != get(1, 0, n, l, r).mx) cout << "wtf " << l << " " << r << "\n"; //cout << dp[l][r].mx << " " << get(1, 0, n, l, r).mx << "\n"; //return get(1, 0, n, l, r); return dp[l][r]; } long long find_shortcut(int N, vector<int> l, vector<int> D, int c){ n = N; for(ll i = 0; i < n; i++){ d[i] = D[i]; ps[i + 1] = ps[i] + l[i]; } bld(1, 0, n); pre(); ll ans = get(0, n).mx; for(ll i = 0; i < n; i++){ for(ll j = i + 1; j < n; j++){ ll C = ps[j] - ps[i] + c; ll x = get(0, i + 1).mxl + get(j, n).mxr - max(0ll, (ps[j] - ps[i]) - c); // cout << "! " << x << "\n"; x = max(x, get(0, i + 1).mx); // cout << "! " << x << "\n"; x = max(x, get(j, n).mx); // cout << "! " << x << "\n"; // cout << "^ " << C << "\n"; ll ptr = i; ll mx1 = min((ll)c, C - c) + d[j], mx2 = min((ll)c, C - c) + d[j]; for(ll k = i; k < j; k++){ mx1 = max(mx1, d[k] + min(ps[k] - ps[i], C + ps[i] - ps[k])); // cout << "! " << min(ps[k] - ps[i], C + ps[i] - ps[k]) << " " <<min(ps[j] - ps[k], C + ps[k] - ps[j]) << "\n"; mx2 = max(mx2, d[k] + min(ps[j] - ps[k], C + ps[k] - ps[j])); while(ptr <= j && ps[ptr] - ps[k] < C + ps[k] - ps[ptr]) ptr++; // cout << "# " << k << " " << ptr << "\n"; x = max(x, d[k] - ps[k] + get(k + 1, ptr).mxr); // cout << "! " << x << "\n"; x = max(x, C + d[k] + ps[k] + get(ptr, j + 1).mxl); // cout << "! " << x << "\n"; } x = max(x, mx2 + get(j + 1, n).mxr - ps[j]); // cout << "! " << x << "\n"; // cout << mx1 << " " << get(0, i).mxl + ps[i] << "\n"; x = max(x, mx1 + get(0, i).mxl + ps[i]); // cout << "! " << x << "\n"; // if(x == 100) cout << "$ " << i << " " << j << "\n"; ans = min(ans, x); } } return ans; } /*int main(){ fast_io; return 0; }*/
#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...