Submission #856475

#TimeUsernameProblemLanguageResultExecution timeMemory
856475nninRice Hub (IOI11_ricehub)C++14
100 / 100
10 ms3812 KiB
#include "ricehub.h" #include<bits/stdc++.h> #define ll long long #define pii pair<ll,int> using namespace std; int besthub(int n, int m, int x[], long long b) { int ans = 0; ll cost = 0; int l = 0; int r = 0; for(int i=0;i<n;i++) { if(i>0) cost += (ll)(x[i]-x[i-1])*(ll)(i-l-r+i-1); if(r<i) { cost += (ll)x[++r]-x[i]; } while(cost>b) { if(x[r]-x[i] > x[i]-x[l]) { cost -= (ll)x[r--]-x[i]; } else { cost -= (ll)x[i]-x[l++]; } } while(true) { if(r<n-1 && x[r+1]-x[i] <= x[i]-x[l]) { cost += (ll)x[++r]-x[i]; cost -= (ll)x[i]-x[l++]; } else if(l>0 && x[i]-x[l-1] < x[r]-x[i]) { cost += (ll)x[i]-x[--l]; cost -= (ll)x[r--]-x[i]; } else if(r<n-1 && cost+(ll)x[r+1]-x[i] <= b) { cost += (ll)x[++r]-x[i]; } else if(l>0 && cost+(ll)x[i]-x[l-1] <= b) { cost += (ll)x[i]-x[--l]; } else { break; } } ans = max(ans, r-l+1); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...