Submission #1199682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199682		thewizardman	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	584 KiB

ricehub

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

int besthub(int n, int _, int a[], long long b) {
  ll l = 0, center = 0, mx = 0, dist = 0;
  for (ll r = 0; r < n; r++) {
    dist += a[r] - a[center];
    while (center < r && (center-l+1) <= (r-center) ) {
      dist -= (r+l-center*2-1)*(a[center+1]-a[center]);
      center++;
    }
    while (dist > b) {
      dist -= a[center]-a[l], l++;
      while (center < r && (center-l+1) <= (r-center) ) {
        dist -= (r+l-center*2-1)*(a[center+1]-a[center]);
        center++;
      }
    }
    mx = max(mx, r-l+1);
    // cout << a[l] << ' ' << a[center] << ' ' << a[r] << ' ' << dist << '\n';
  }
  return mx;
}

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