Submission #853097

#TimeUsernameProblemLanguageResultExecution timeMemory
853097waldiShortcut (IOI16_shortcut)C++17
31 / 100
2045 ms600 KiB
#include <bits/stdc++.h> #include "shortcut.h" #define FOR(i,p,k) for(int i=(p);i<=(k);++i) #define REP(i,n) FOR(i,0,(n)-1) #define inf 1000000000000000000ll using namespace std; typedef long long ll; ll find_shortcut(int n, vector<int> l_int, vector<int> d_int, int c_int){ vector<ll> l(n), d(n); REP(i, n) l[i] = l_int[i], d[i] = d_int[i]; ll c = c_int; vector<ll> pref(n, 0ll); FOR(i, 1, n-1) pref[i] = pref[i-1]+l[i-1]; ll lewo_ogolem = -inf; ll prawo_ogolem = -inf; REP(i, n){ lewo_ogolem = max(lewo_ogolem, d[i]-pref[i]); prawo_ogolem = max(prawo_ogolem, d[i]+pref[i]); } ll wyn = lewo_ogolem+prawo_ogolem; REP(kon, n) REP(poc, kon){ ll odl = 0ll; ll lewopoc = -inf; FOR(i, 0, poc-1){ odl = max(odl, lewopoc+d[i]+pref[i]); lewopoc = max(lewopoc, d[i]-pref[i]); } ll prawokon = -inf; for(int i = n-1; i >= kon+1; --i){ odl = max(odl, prawokon+d[i]-pref[i]); prawokon= max(prawokon, d[i]+pref[i]); } odl = max(odl, lewopoc+prawokon-pref[kon]+pref[poc]+c); //printf("odl: %lld\n", odl); //printf("%lld %lld\n", lewo, prawo); ll cykl = pref[kon]-pref[poc]+c; FOR(i, poc, kon){ ll dopoc = pref[i]-pref[poc]; ll dokon = pref[kon]-pref[i]; dopoc = min(dopoc, cykl-dopoc); dokon = min(dokon, cykl-dokon); odl = max(odl, lewopoc+dopoc+pref[poc]+d[i]); odl = max(odl, dokon+prawokon-pref[kon]+d[i]); } /*int it = poc; FOR(i, poc, kon){ while(it < kon && pref[it+1]-pref[i] <= (cykl>>1)) ++it; odl = max(odl, pref[it]-pref[i]+d[i]+d[it]); }*/ if(odl >= wyn) continue; FOR(i, poc, kon){ FOR(j, i+1, kon){ ll t = pref[j]-pref[i]; t = min(t, cykl-t); odl = max(odl, t+d[i]+d[j]); if(odl >= wyn) break; } if(odl >= wyn) break; } /*REP(j, n) REP(i, j){ if(i <= poc && j >= kon) continue; if(i <= poc && j <= poc) continue; if(i >= kon && j >= kon) continue; ll t = pref[j]-pref[i]; t = min(t, c + abs(pref[i]-pref[poc]) + abs(pref[kon]-pref[j])); odl = max(odl, t+d[i]+d[j]); }*/ //printf("%d %d: %lld\n", poc, kon, odl); wyn = min(wyn, odl); } return wyn; }
#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...