# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
667480 | 2022-12-01T14:26:12 Z | 1bin | Rice Hub (IOI11_ricehub) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "ricehub.h" using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 1e5 + 5; ll R, L, X[NMAX], B; ll go(ll k){ ll a = 0, b = 0, c, m, p = 0; for(int i = 0; i < k / 2; i++) a += X[i]; for(int i = k / 2; i < k; i++) b += X[i]; if(k & 1) p = X[k / 2]; c = -a + b - p; for(int i = k; i < R; i++){ m = i - (k + 1) / 2; a += -X[i - k] + X[m]; b += -X[m] + X[i]; if(k & 1) p = X[m + 1]; c = min(c, -a + b - p); } return c <= B; } ll besthub(int R_, int L_, int X_[], ll B_){ R = R_; L = L_; B = B_; for(int i = 0; i < R; i++) X[i] = X_[i]; ll l = 1, r = R, m; while(l < r){ m = (l + r + 1) / 2; if(go(m)) l = m; else r = m - 1; } return l; } /* int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> R >> L >> B; for(int i = 0; i < R; i++) cin >> X[i]; cout << besthub(R, L, X, B); return 0; } */