# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
737205 | 2023-05-06T20:36:08 Z | ETheBest3 | 쌀 창고 (IOI11_ricehub) | C++14 | 0 ms | 0 KB |
#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; }