Submission #1217284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217284		LeonidCuk	Rice Hub (IOI11_ricehub)	C++20	100 / 100	15 ms	3144 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
vector<long long int>l,r,v;
long long vrni(long long int l1,long long int m,long long a)
{
    long long int s=(m+l1)/2;
    return r[s]-r[m]-(m-s)*v[s]+l[s]-l[l1]-(s-l1)*(a-v[s])+v[m]-v[l1];
}
int besthub(int n, int x, int v1[], long long k)
{
    l.resize(n);
    r.resize(n);
    v.resize(n);
    for(int i=0;i<n;i++)v[i]=v1[i];
    long long sum=1;
    int res=0;
    r[n-1]=v[n-1];
    l[0]=x-v[0];
    for(int i=1;i<n;i++)
    {
        l[i]=l[i-1]+x-v[i];
    }
    for(int i=n-2;i>=0;i--)
    {
        r[i]=r[i+1]+v[i];
    }
    for(int i=0;i<n;i++)
    {
        int l1=i,r1=n-1;
        while(l1+1<r1)
        {
            int m=(l1+r1)/2;
            sum=vrni(i,m,x);
            if(sum<=k)l1=m;
            else r1=m;
        }
        sum=vrni(i,r1,x);
        if(sum<=k)res=max(res,r1-i+1);
        res=max(res,l1-i+1);
    }
    return res;
}

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