# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
724739 | 2023-04-15T20:21:18 Z | Bogdan1110 | Rice Hub (IOI11_ricehub) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);} #define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);} #define ll long long #define ull unsigned long long #define pqueue priority_queue #define pb push_back #define fi first #define se second #define ld long double #define pii pair<int,int> #define pll pair<long long,long long> #define all(a) (a).begin(), (a).end() #define mp make_pair using namespace std; // order_of_key -> # less than k // find_by_order -> k-th element // pq max element void files() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } const double eps = 0.00000001; const int NMAX = 100010; const ll inf = LLONG_MAX/3; const ll modi = 998244353; ll s1[NMAX], s2[NMAX], X[NMAX]; #define SUM(l,r) (s1[r]-(l?s1[l-1]:0)) ll calc(int l, int r) { int mid = (l+r)/2; ll res = (mid-l+1)*(X[mid]) - SUM(l,mid); res += SUM(mid,r) - (r-mid+1)*(X[mid]); return res; } ll besthub(ll n, ll L, ll x[], ll b) { for (int i = 0 ; i < n ; i++) { s1[i] = x[i]; X[i] = x[i]; if ( i ) s1[i] += s1[i-1]; } ll res = 1; ll l = 0; ll r = 1; while(r<n) { //cout << l << ' ' << r << endl; ll temp = calc(l,r); if (temp <= b) { r++; res = max(res, r-l); } else { l++; } } return res; }