| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 504055 | Newtech66 | Rice Hub (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;
using lol=long long int;
#define endl "\n"
const lol mod1=1e9+7,mod2=998244353;
const lol inf=1e18+8;
const double eps=1e-12;
const double PI=acos(-1.0);
const int N=2e5+5;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool ok(const vector<lol>& p,int n,lol B,int k)
{
auto query=[&](int l,int r){
if(l>r) return 0ll;
return p[r]-(l?p[l-1]:0);
};
for(int i=0;i+k-1<n;i++)
{
int pos=i+k/2;
lol chk=0;
if(i<=pos) chk+=(pos-i+1)*query(pos,pos)-query(i,pos);
if(pos+1<=i+k-1) chk+=query(pos+1,i+k-1)-(i+k-1-pos)*query(pos,pos);
if(chk<=B) return true;
}
return false;
}
int besthub(int R,int L,int X[],lol B)
{
vector<lol> p{X,X+R};
partial_sum(p.begin(),p.end(),p.begin());
int l=1,r=R,mid,ans;
while(l<=r)
{
mid=l+(r-l)/2;
if(ok(p,R,B,mid))
{
ans=mid;
l=mid+1;
}else r=mid-1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
//cin>>_;
while(_--)
{
int R,L;
lol B;
cin>>R>>L>>B;
int X[R];
for(int i=0;i<R;i++) cin>>X[i];
cout<<besthub(R,L,X,B);
}
return 0;
}