| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1236661 | JelaByteEngineer | 쌀 창고 (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#include "ricehub.h"
using namespace std;
#define ll long long
bool ok (int mid, int b, int n, vector <ll> &x, vector <ll> &pref)
{
//cout<<"mid je: "<<mid<<endl;
for (int i=0; i<=n-mid; i++)
{
//cout<<"prvi je na poz: "<<i<<endl;
int prf=pref[i+mid-1]-pref[i-1]*(i>0);
prf/=mid;
//cout<<"prosek prvih mid je: "<<prf<<endl;
int up=upper_bound(x.begin(), x.end(), prf)-x.begin();
if (upper_bound(x.begin(), x.end(), prf)==x.end()) up=prf;
//cout<<"up je: "<<up<<endl;
//cout<<"budzet je: "<<-pref[up-1]*(up>0)+pref[i-1]*(i>0)+(up-i)*prf+pref[i+mid-1]-pref[up-1]-(mid-up+i)*prf<<endl;
if (-pref[up-1]+pref[i-1]*(i>0)+(up-i)*prf+pref[i+mid-1]-pref[up-1]-(mid-up+i)*prf<=b) return true;
}
return false;
}
int besthub (int R, int L, int X[], int B)
{
int n=R;
vector <ll> x(n);
for (int i=0; i<n; i++) x[i]=X[i];
vector <ll> pref(n);
for (int i=0; i<n; i++) pref[i]=pref[i-1]*(i>0)+X[i];
int l=1, r=n, ans=1;
while (l<=r)
{
int mid=l+(r-l)/2;
if (ok(mid, B, n, x, pref)) {ans=max(ans, mid); l=mid+1;}
else r=mid-1;
}
return ans;
}