Submission #615749

#	Time	Username	Problem	Language	Result	Execution time	Memory
615749		Minindu2006	Rice Hub (IOI11_ricehub)	C++14	100 / 100	14 ms	3120 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> pref, arr;
ll getSum(int a, int b)
{
  return pref[b] - pref[a - 1];
}
int besthub(int R, int L, int X[], long long B)
{
  pref.resize(R + 1, 0);
  arr.resize(R + 1);
  for(int i=1;i<=R;i++)
    pref[i] += pref[i - 1] + X[i - 1], arr[i] = X[i - 1];
  int ans = -1;
  // for(int i=1;i<=R;i++)
  // {
  //   for(int j=i;j<=R;j++)
  //   {
  //     int mid = (i + j) / 2;
  //     ll cur = (arr[mid] * (mid - i) - getSum(i, mid - 1)) + (getSum(mid + 1, j) - arr[mid] * (j - mid));
  //      cout << cur << '\n';
  //     if(cur <= B)
  //       ans = max(j - i + 1, ans);
  //   }
  // }
  int i = 1, j = 1;
  while(R - j >= 0)
  {
    int mid = (i + j) / 2;
    ll cur = (arr[mid] * (mid - i) - getSum(i, mid - 1)) + (getSum(mid + 1, j) - arr[mid] * (j - mid));
    if(cur <= B)
      ans = max(j - i + 1, ans), j++;
    else
      i++;
  }
  return ans;
}

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