# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
737205 | ETheBest3 | Rice Hub (IOI11_ricehub) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "ricehub.h"
#include<bits/stdc++.h>
#define lli long long
const lli MAXN=100005;
lli pref[MAXN];
int besthub(int R, int L, int X[], long long B)
{
for(lli i=0; i<R; i++){
if(i==0)pref[i]=X[i];
else pref[i]=pref[i-1]+X[i];
}
lli p1=0, p2=0, p3=0, now=0, sum=0, ans=0;
for(;p2<R; p2++){
now=pref[p2]/(p2+1);
while(p3<p2 and X[p3+1]<=now)p3++;
sum=(pref[p2]-pref[p3])-now*(p2-p3)+now*(p3+1)-pref[p3];
if(sum>B)break;
}
if(sum<=B)return p2;
ans=max(ans, p2);
p2--;
for(p1=0;p1<R; p1++){
for(;p2<R; p2++){
now=(pref[p2]-pref[p1])/(p2-p1);
while(p3<p2 and X[p3+1]<=now)p3++;
sum=(pref[p2]-pref[p3])-now*(p2-p3)+now*(p3-p1)-(pref[p3]-pref[p1]);
if(sum>B)break;
}
ans=max(ans, p2-p1-1);
p2--;
}
return ans;
}