Submission #651494

#	Time	Username	Problem	Language	Result	Execution time	Memory
651494		andrei_boaca	Rice Hub (IOI11_ricehub)	C++14	100 / 100	18 ms	3328 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
//#include "grader.cpp"
typedef long long ll;
ll n,m,maxi,v[200005],s[200005];
bool check(int i,int j,int poz)
{
    if(poz<i||poz>j)
        return 0;
    ll inlft=(poz-i+1);
    ll slft=s[poz]-s[i-1];
    ll suma=0;
    suma+=inlft*v[poz]-slft;

    ll inrgt=(j-poz+1);
    ll srgt=s[j]-s[poz-1];
    suma+=srgt-inrgt*v[poz];
    return suma<=maxi;
}
bool ok(int lg)
{
    for(int i=1;i<=n;i++)
    {
        int j=i+lg-1;
        if(j>n)
            break;
        int mij=(i+j)/2;
        for(int poz=mij-1;poz<=mij+1;poz++)
            if(check(i,j,poz))
                return 1;
    }
    return 0;
}
int besthub(int R, int L, int X[], long long B)
{
    n=R;
    m=L;
    maxi=B;
    for(int i=0;i<n;i++)
        v[i+1]=X[i];
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+v[i];
    int ans=0;
    int st=1;
    int dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(ok(mij))
        {
            ans=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return ans;
}

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