| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 155834 | m1sch3f | 쌀 창고 (IOI11_ricehub) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
// types - only for stuff used a lot
using ll = long long;
#define vv vector
#define Pp pair
// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);
// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size())
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi
// Debugging
#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif
#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec) {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}
const int mod = 1e9+7, oo = 1e9;
const ll loo = 1e18;
// Functions
ll modpow(ll a, ll b) {
ll ans = 1; // faster modpow than recursive
for (; b; b/=2,a=a*a%mod)
if (b&1) ans = (ans*a)%mod;
return ans;
}
ll gcd(ll a, ll b) {
while (a) b%=a,swap(a,b);
return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)
/*
ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS
*/
const bool DEBUG = 1;
using pll = pair<ll,ll>;
int best_hub(int N, int L, int rem[], ll B) {
ll C[N];
f(i,0,N) C[i] = i?rem[i]+C[i-1]:rem[i];
vector<int> X(N);
f(i,0,N) X[i] = rem[i];
auto sum = [&](int i, int j) {
if (i>j) return 0LL;
return C[j]-(i?C[i-1]:0);
};
auto fu = [&](int i, int l) {
// to the left
int x = lower_bound(begin(X),end(X),X[i]-l)-begin(X);
int y = upper_bound(begin(X),end(X),X[i]+l)-begin(X)-1;
return pll(1LL*(i-x)*X[i]-sum(x,i-1)+
sum(i+1,y)-1LL*(y-i)*X[i],y-x+1);
};
ll ans = 0;
f(i,0,N) {
int lo = 0, hi = L;
while (lo <= hi) {
int mid = lo+hi>>1;
if (fu(i,mid).first <= B)
lo = mid+1;
else hi = mid-1;
}
re(ans,fu(i,hi).second);
}
return ans;
}