Submission #24945

#TimeUsernameProblemLanguageResultExecution timeMemory
24945HiasatShortcut (IOI16_shortcut)C++14
38 / 100
2000 ms81376 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3000; const ll INF = 1e18; ll L[N],R[N],mxL[N],mxR[N],pre[N]; vector<int> d,l; bool vis[N][N]; ll dp[N][N]; int n; ll c; bool check(ll mid){ for(int len = 1; len <= n ; ++len){ for(int i = n-len ; i>=0 ; --i){ int j = i + len - 1; if(len==1){ dp[i][j]= INF; continue; } if(pre[j]-pre[i] +d[i]+d[j] > mid) dp[i][j]=(pre[j]-pre[i]) - d[i] - d[j]; else dp[i][j]=INF; /* if(i == 1 && j == 2){ cout << (pre[j]-pre[i]) + d[i] + d[j] << endl; }*/ dp[i][j] = min(dp[i][j],min(dp[i+1][j],dp[i][j-1])); } } // cout << dp[0][3] << endl; memset(vis,0,sizeof vis); for(int i = 0 ; i < n ; ++i){ if(mxL[i] > mid) continue; ll fage3 = -INF; ll csum = 0; for (int j = i+1; j < n; ++j){ csum += l[j-1]; if(L[j]+d[j] > mid) fage3 = max(fage3,L[i]+c+d[j]); if(fage3 > mid) break; /* if(i == 1 && j == 3){ cout << fage3 << " " << L[i] << " " << d[j] << " " << csum+c-dp[i][j] << endl; }*/ /* if(i == 1 && j == 2){ cout << dp[i][j] << " " << csum << endl; }*/ if(min(csum,c)+L[i]+R[j]<=mid && mxR[j]<=mid && (dp[i][j] ==INF || csum+c-dp[i][j]<=mid)){ vis[i][j] = 1; } if(j != n-1) fage3 += l[j]; } } for(int i = n-1 ; i >= 0 ;--i){ if(mxR[i] > mid) continue; ll fage3 = -INF; for (int j = i-1; j>= 0 ;j--){ if(R[j]+d[j] > mid) fage3 = max(fage3,R[i]+c+d[j]); if(fage3 > mid) break; if(mxL[j]<=mid && vis[j][i]){ //cout << "HERE " << j << " " << i << endl; return true; } if(j != 0) fage3 += l[j-1]; } } return false; } ll find_shortcut(int n, vector<int> l, vector<int> d, int c){ if(n>3000) return -1; ::n=n; ::d=d; ::c=c; ::l=l; for (int i = 0; i < n; ++i){ L[i] = d[i]; if(i) pre[i] = l[i-1] + pre[i-1]; if(i) L[i] = max(L[i-1]+l[i-1],L[i]); mxL[i] = max(i?mxL[i-1]:0,d[i]+ (i?L[i-1]+l[i-1]:0)); } for(int i = n - 1 ; i >= 0 ; i--){ R[i] = d[i]; if(i != n-1) R[i] = max(R[i],R[i+1]+l[i]); mxR[i] = max(i!=n-1?mxR[i+1]:0,d[i] + (i!=n-1?R[i+1]+l[i]:0)); } //cout << "HASAN " << check(100) << endl; //return 0; ll lo = *max_element(d.begin(),d.end()) , hi = 1e9*(N+3),best = -1; while(lo <= hi){ ll mid = (lo + hi)/2; // cout << mid << " " << check(mid) << endl; if(check(mid)){ best = mid; hi = mid -1; }else{ lo = mid + 1; } } assert(best!=-1); return best; }
#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...