| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301105 | filip1111 | 쌀 창고 (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
using ll = long long;
const ll N=1e5;
ll pref[N+99];
ll n,L;
long long B;
vector<ll>V;
bool f(ll k)
{
for(ll i=1;i<=n-k+1;i++)
{
ll srodek=(i+i+k-1)/2;
long long srodek_w=V[srodek];
long long ans=0;
ans+=(srodek_w)*(srodek-(i-1))-(pref[srodek]-pref[i-1]);
// if(k==4)
// {
// cout << ans << " " << srodek_w << " " << srodek << " " << pref[srodek] <<" - " << pref[i-1]<< '\n';
// cout << srodek-(i-1) << '\n';
// }
ans+=(pref[i+k-1]-pref[srodek])-(srodek_w)*(i+k-1-srodek);
// if(k==4)
// {
// cout << ans << " " << pref[i+k-1] <<" - " << pref[srodek]<< '\n';
// cout << srodek_w << " * " <<i+k-1-srodek << '\n';
// }
if(ans<=B)return 1;
}
return 0;
}
int besthub(int _R, int _L, int X[], long long _B){
B = _B;
n = _R;
L = _L;
V.resize(n + 1);
for(int i = 0; i < n; i++)V[i+1] = X[i];
//sort(all(V));
for(ll i=1;i<=n;i++)
{
pref[i]=pref[i-1]+V[i];
}
// for(ll i=1;i<=n;i++)
// {
// cout << f(i)<<"X" << '\n';
// }
ll l=1,r=n+1;
while(r-l>1)
{
ll s=(l+r)/2;
if(f(s))l=s;
else r=s;
}
return l;
}
int main(){
}