Submission #998308

#	Time	Username	Problem	Language	Result	Execution time	Memory
998308		Alfraganus	Rice Hub (IOI11_ricehub)	C++17	100 / 100	13 ms	4448 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;

int besthub(int n, int l, int a[], long long b){
  vector<long long> pref(n + 1);
  for(int i = 1; i <= n; i ++)
    pref[i] = pref[i - 1] + a[i - 1];
  auto good = [&](int x){
    for(int i = 0; i < n - x + 1; i ++){
      long long middle = a[i + x / 2], sum = middle * (x / 2 + 1) - pref[i + x / 2 + 1] + pref[i] + pref[i + x] - pref[i + x / 2 + 1] - middle * (x - x / 2 - 1);
      if(sum <= b)
        return true;
    }
    return false;
  };
  int left = 1, right = n;
  while(left < right){
    int mid = (left + right + 1) >> 1;
    if(good(mid))
      left = mid;
    else
      right = mid - 1;
  }
  return left;
}

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