Submission #551239

#TimeUsernameProblemLanguageResultExecution timeMemory
551239AriaHRice Hub (IOI11_ricehub)C++17
100 / 100
17 ms1496 KiB
#include "ricehub.h" /* Im the best and i work like that */ #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(),x.end() #define Mp make_pair #define point complex #define endl '\n' #define SZ(x) (int)x.size() #define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout); #define mashtali return cout << "Hello, World!", 0; const int N = 1e6 + 10; const int LOG = 20; const ll mod = 1e9 + 7; const ll inf = 8e18; const double pi = acos(-1); const ld eps = 1e-18; const ld one = 1.; ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; } mt19937 rng(time(nullptr)); int n; ll ps[N]; inline ll get(int l, int r) { return ps[r] - (l <= 0? 0 : ps[l - 1]); } int besthub(int _n, int L, int X[], ll B) { n = _n; for(int i = 0; i < n; i ++) { ps[i] += X[i]; ps[i + 1] += ps[i]; } int ans = 1; for(int i = 0; i < n; i ++) { int d = 0, up = min(i, n - 1 - i) + 1; while(up - d > 1) { int mid = (up + d) >> 1; ll cu = -get(i - mid, i) + get(i, i + mid); if(cu <= B) { d = mid; ans = max(ans, d << 1 | 1); if(i + mid + 1 < n && cu + X[i + mid + 1] - X[i] <= B) { ans = max(ans, d * 2 + 2); } } else up = mid; } if(i + 1 < n && X[i + 1] - X[i] <= B) ans = max(ans, 2); } return ans; } /* check corner case(n = 1?), watch for negetive index or overflow */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...