Submission #1236692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236692		JelaByteEngineer	Rice Hub (IOI11_ricehub)	C++20	17 / 100	0 ms	328 KiB

ricehub

#include <bits/stdc++.h>
//#include "ricehub.h"
using namespace std;
#define ll long long
bool ok (int mid, ll 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;
        ll 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;
        prf++;
        //cout<<"prosek prvih mid je: "<<prf<<endl;
        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 ((up>0? -pref[up-1]:0)+(i>0? pref[i-1]:0)+(up-i)*prf+pref[i+mid-1]-(up>0? pref[up-1]:0)-(mid-up+i)*prf<=b) return true;
    }
    return false;
}
int besthub (int R, int L, int X[], ll 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;
}

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