Submission #1031661

#TimeUsernameProblemLanguageResultExecution timeMemory
1031661pccShortcut (IOI16_shortcut)C++17
0 / 100
41 ms72324 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC taget("avx2,popcnt,sse4") #define pll pair<ll,ll> #define fs first #define sc second #define pii pair<int,int> #define ll long long #define DEBUG(T) cerr<<#T<<":"<<T<<endl; const ll inf = 1e18; const int mxn = 3030; ll pref[mxn]; ll arr[mxn]; int C,N; ll dp[mxn][mxn]; ll P[mxn],S[mxn]; ll pans[mxn],sans[mxn]; ll brr[mxn]; ll chain(ll R,int s,int e){ return pref[e]-pref[s]+brr[e]+brr[s]; } ll cycle(ll R,int s,int e){ return R+C-(pref[e]-pref[s])+brr[s]+brr[e]; } ll calc(int a,int b){ if(dp[a][b] != -1)return dp[a][b]; if(a == b)return dp[a][b] = pans[N-1]; for(int i = a;i<=b;i++)brr[i] = arr[i]; brr[a] = P[a],brr[b] = S[b]; ll ans = *max_element(brr+a,brr+b+1); ans = max({ans,pans[a],sans[b]}); ll cyc = -inf; ll R = pref[b]-pref[a]; ll re = 0; int ptr = a; multiset<ll> st; st.insert(-inf); for(int i = a;i<=b;i++){ while(ptr<i&&cycle(R,ptr,i)<chain(R,ptr,i)){ st.erase(st.find(brr[ptr]-pref[ptr])); cyc = max(cyc,brr[ptr]+pref[ptr]); ptr++; } ll chn = *st.rbegin(); ans = max({ans,pref[i]+brr[i]+chn,cyc+brr[i]-pref[i]+R+C}); st.insert(brr[i]-pref[i]); } return dp[a][b] = ans; } void init(){ ll pp = -inf; for(int i = 0;i<N;i++){ pans[i] = arr[i]; if(i)pans[i] = max(pans[i],pans[i-1]); pans[i] = max(pans[i],arr[i]+pref[i]+pp); pp = max(pp,-pref[i]+arr[i]); } pp = -inf; for(int i = N-1;i>=0;i--){ sans[i] = arr[i]; if(i != N-1)sans[i] = max(sans[i],sans[i+1]); sans[i] = max(sans[i],arr[i]-pref[i]+pp); pp = max(pp,pref[i]+arr[i]); } P[0] = arr[0];S[N-1] = arr[N-1]; for(int i = 1;i<N;i++)P[i] = max(P[i-1]+pref[i]-pref[i-1],arr[i]); for(int i = N-2;i>=0;i--)S[i] = max(S[i+1]+pref[i+1]-pref[i],arr[i]); } ll ans[mxn]; void dc(int tl,int tr,int l,int r){ int mid = (l+r)>>1; assert(tl<=mid); int good = tl; for(int i = tl;i<=min(mid,tr);i++){ if(calc(good,mid)>=calc(i,mid))good = i; } ans[mid] = min(ans[mid],calc(good,mid)); cerr<<"DC: "<<tl<<' '<<tr<<' '<<l<<' '<<r<<' '<<mid<<":"<<good<<','<<calc(good,mid)<<endl; if(l != mid)dc(good,tr,l,mid-1); if(mid != r)dc(tl,good,mid+1,r); return; } void f(int l,int r){ if(l == r){ ans[l] = min(ans[l],pans[N-1]); return; } int mid = (l+r)>>1; dc(l,mid,mid+1,r); return; } long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){ memset(dp,-1,sizeof(dp)); N = n,C = c; for(int i = 0;i<N;i++)arr[i] = d[i]; for(int i = 0;i+1<N;i++){ pref[i+1] = pref[i]+l[i]; } init(); fill(ans,ans+N,inf); f(0,N-1); return *min_element(ans,ans+N); }

Compilation message (stderr)

shortcut.cpp:6: warning: ignoring '#pragma GCC taget' [-Wunknown-pragmas]
    6 | #pragma GCC taget("avx2,popcnt,sse4")
      | 
shortcut.cpp: In function 'long long int calc(int, int)':
shortcut.cpp:43:5: warning: unused variable 're' [-Wunused-variable]
   43 |  ll re = 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...