Submission #245240

#	Time	Username	Problem	Language	Result	Execution time	Memory
245240		kimbj0709	Rice Hub (IOI11_ricehub)	C++14	100 / 100	25 ms	1024 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
#include "ricehub.h"
int besthub(int R, int L, int X[], long long B){
  long long ans = 1;
  long long currsum = 0;
  long long left = 0,right = -1;
  for(long long i=0;i<R;i++){
    currsum += (X[i]-X[i-1])*(i-left);
    currsum -= (X[i]-X[i-1])*(right-i+1);
    right = max(right,i);
    while(currsum>B){
      if(abs(X[i]-X[left])>abs(X[i]-X[right])){
        currsum -= abs(X[i]-X[left]);
        left++;
      }
      else{
        currsum -= abs(X[i]-X[right]);
        right--;
      }
    }
    while(right!=R-1){
      if(abs(X[i]-X[left])>abs(X[i]-X[right+1])){
        currsum -= abs(X[i]-X[left]);
        currsum += abs(X[i]-X[right+1]);
        left++;
        right++;
      }
      else{
        break;
      }
    }
    while(currsum<=B){
        long long l,r;
        if(left==0){
            l = INT_MAX;
        }
        else{
            l = abs(X[i]-X[left-1]);
        }
        if(right==R-1){
            r = INT_MAX;
        }
        else{
            r = abs(X[i]-X[right+1]);
        }
        long long mini = min(l,r);
        if(currsum+mini>B||(l==INT_MAX&&r==INT_MAX)){
            break;
        }
        if(l<r){
            left--;
        }
        else{
            right++;
        }
        currsum += mini;
    }
    ans = max(ans,right-left+1);
  }
  return ans;
}

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