Submission #504057

#	Time	Username	Problem	Language	Result	Execution time	Memory
504057		Newtech66	Rice Hub (IOI11_ricehub)	C++17	100 / 100	13 ms	2524 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;

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;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, lol)':
ricehub.cpp:36:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     return ans;
      |            ^~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32