Submission #787485

#	Time	Username	Problem	Language	Result	Execution time	Memory
787485		acatmeowmeow	Rice Hub (IOI11_ricehub)	C++11	100 / 100	15 ms	2496 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
long long prefix[N + 5];

int besthub(int R, int L, int X[], long long B) {
	for (int i = 1; i <= R; i++) prefix[i] = prefix[i - 1] + (long long)X[i - 1];
	int l = 1, r = R, ans = 0;
	while(l <= r) {
		int m = (l + r)/2, valid = 0;
		for (int i = m; i <= R; i++) {
			int j = i - m + 1, median = (i + j)/2;
			long long f = prefix[i] - prefix[median] - (long long)(i - median)*X[median - 1];
			long long se = (long long)(median - j + 1)*X[median - 1] - (prefix[median] - prefix[j - 1]);
			valid |= f + se <= B;
		}
		if (valid) ans = m, l = m + 1;
		else r = m - 1;
	}
	return ans;
}

/*#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_R  1000000

static int R, L;
static long long B;
static int X[MAX_R];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

static void read_input()
{
  int i;
  //my_assert(3==scanf("%d %d %lld",&R,&L,&B));
  cin >> R >> L >> B;
  for(i=0; i<R; i++)
   // my_assert(1==scanf("%d",&X[i]));
   cin >> X[i];
  //my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = besthub(R,L,X,B);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect.  Returned %d instead of %d.\n",ans,solution);

  return 0;
}*/

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