Submission #14777

#	Time	Username	Problem	Language	Result	Execution time	Memory
14777		minsu	Rice Hub (IOI11_ricehub)	C++14	100 / 100	27 ms	6496 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 111111;
typedef long long lld;
lld psum[MAXR];
lld interval( int i, int j ) {
  // [i, j]
  int m = (i + j)/2, x = psum[m] - psum[m-1];
  return ( 2*m - i - j ) * 1LL * x - psum[m-1] + psum[i-1] + psum[j] - psum[m];
}
int besthub(int R, int L, int X[], long long B)
{
  for(int i=1; i<=R; i++) psum[i] = psum[i-1] + X[i-1];
  int j = 1, ret = 0;
  for(int i=1; i<=R; i++)
    while( j<=R && interval(i, j) <= B ) ret = max( ret, j-i+1), j++;
  return ret;
}

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