Submission #1100324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100324		mm77	Rice Hub (IOI11_ricehub)	C++14	100 / 100	14 ms	3684 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
long long r,l,b,x[N];
bool ok(int mid)
{
    long long left=0,right=mid-1,sr=(left+right)/2,res=0;
    for(int i=left;i<=right;i++)
    {
        res+=abs(x[i]-x[sr]);
    }
    while(right<r)
    {
        if(res<=b)return true;
        res+=(sr-left+1)*(x[sr+1]-x[sr]);
        res-=(right-sr)*(x[sr+1]-x[sr]);
        res-=x[sr+1]-x[left];
        res+=x[right+1]-x[sr+1];
        sr++,right++,left++;
    }
    return false;
}
int besthub(int r2,int l2,int x2[],long long b2)
{
    r=r2,l=l2,b=b2;
    for(int i=0;i<r;i++)x[i]=x2[i];
    int pocz=1,kon=r+1;
    while(pocz+1<kon)
    {
        int mid=(pocz+kon)/2;
        if(ok(mid))pocz=mid;
        else kon=mid;
    }
    return pocz;
}

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