Submission #64666

#	Time	Username	Problem	Language	Result	Execution time	Memory
64666		alenam0161	Rice Hub (IOI11_ricehub)	C++17	100 / 100	34 ms	7148 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
int besthub(int R, int L, int X[], long long B)
{
  int l=1;
  int r=R;
  int ans=1;
  while(l<=r){
    int mid=(l+r)/2;
    int curpos=0;
    long long hwl=1;
    long long hwr=mid-1;
    long long cur=0;
    int cl=0;int cr=mid-1;
    for(int i=1;i<mid;++i){
        cur+=X[i]-X[0];
    }
  //  cout<<mid<<" "<<cur<<endl;
    if(cur<=B){
        ans=mid;
        l=mid+1;
        continue;
    }
   // cout<<"h"<<endl;
    bool ok=true;
    while(cr<R){
        while(hwl<hwr&&curpos<cr){
            long long ds=(X[curpos+1]-X[curpos]);
            cur-=(hwr-hwl)*ds;
            hwl++;hwr--;
            curpos++;
        }
    //    cout<<cur<<" "<<hwl<<" "<<hwr<<" "<<cl<<" "<<cr<<endl;
        if(cur<=B){
            ok=false;
            break;
        }
        cl++;cr++;
        hwl--;hwr++;
        cur-=X[curpos]-X[cl-1];
        cur+=X[cr]-X[curpos];
    }
    if(ok){
        r=mid-1;
    }
    else{
        ans=mid;
        l=mid+1;
    }
  }
  return ans;
}

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