Submission #520492

#	Time	Username	Problem	Language	Result	Execution time	Memory
520492		krit3379	Rice Hub (IOI11_ricehub)	C++17	100 / 100	18 ms	2512 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;

long long qs[100005],l,r,mid,new_mid,new_val,ans;

int besthub(int n, int m, int x[100005], long long b){
    int i;
    for(i=n;i>0;i--)x[i]=x[i-1];
    x[0]=0;
    for(i=1;i<=n;i++)qs[i]=qs[i-1]+x[i];
    l=1,r=1,mid=1;
    for(l=1;l<=n;l++){
        while(1){
            if(r==n)break;
            new_mid=(l+r+1)/2;
            new_val=x[new_mid]*(new_mid-l)-qs[new_mid-1]+qs[l-1]+qs[r+1]-qs[new_mid]-x[new_mid]*(r+1-new_mid);
            if(new_val<=b)mid=new_mid,r++;
            else break;
        }
        ans=max(ans,r-l+1);
    }
    return ans;
}

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