Submission #891803

#	Time	Username	Problem	Language	Result	Execution time	Memory
891803		ind1v	Rice Hub (IOI11_ricehub)	C++11	100 / 100	15 ms	3676 KiB

ricehub

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

using namespace std;

const int R = 1e5 + 5;

int xx[R];
long long s[R];

long long sum(int i, int j) {
  if (i > j) {
    return 0;
  }
  return (i == 0 ? s[j] : s[j] - s[i - 1]);
}

long long cost(int i, int j) {
  int mid = (i + j) >> 1;
  long long res = 0;
  res += 1LL * xx[mid] * (mid - i + 1) - sum(i, mid);
  if (mid + 1 <= j) {
    res += sum(mid + 1, j) - 1LL * xx[mid] * (j - mid);
  }
  return res;
}

int besthub(int r, int l, int x[], long long b) {
  for (int i = 0; i < r; i++) {
    s[i] = (i == 0 ? x[i] : x[i] + s[i - 1]);
    xx[i] = x[i];
  }
  int ans = 0;
  for (int i = 0, j = 0; i < r; i++) {
    while (j + 1 <= i && cost(j, i) > b) {
      j++;
    }
    ans = max(ans, i - j + 1);
  }
  return ans;
}

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