Submission #168935

#	Time	Username	Problem	Language	Result	Execution time	Memory
168935		AlexLuchianov	Rice Hub (IOI11_ricehub)	C++14	100 / 100	518 ms	3448 KiB

ricehub

#include "ricehub.h"
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int n, lim;
ll v[1 + nmax], sum[1 + nmax];

///returns position of the last farm with coordinate lower (or equal) than target

int lowerthan(int target){
  int x = 0;
  for(int jump = (1 << 20); 0 < jump; jump /= 2)
    if(x + jump <= n && v[x + jump] <= target)
      x += jump;
  return x;
}

ll tryit(int pos, ll dist, ll budget){
  int pos2 = lowerthan(v[pos] + dist), pos3 = lowerthan(v[pos] - dist - 1) + 1;

  ll result = ((sum[pos2] - sum[pos - 1]) - (pos2 - pos + 1) * v[pos]);
  ll result2 = (pos - pos3 + 1) * v[pos] - (sum[pos] - sum[pos3 - 1]);

  return result + result2 <= budget;
}

ll solve(int pos, ll budget){
  int dist = 0;
  for(int jump = (1 << 30); 0 < jump; jump /= 2){
    if(dist + jump <= lim && tryit(pos, dist + jump, budget))
      dist += jump;
  }
  dist++;


  int pos2 = lowerthan(v[pos] + dist), pos3 = lowerthan(v[pos] - dist - 1) + 1;

  ll result = ((sum[pos2] - sum[pos - 1]) - (pos2 - pos + 1) * v[pos]);
  ll result2 = (pos - pos3 + 1) * v[pos] - (sum[pos] - sum[pos3 - 1]);
  result = result + result2;


  if(result <= budget)
    return (pos2 - pos3 + 1);
  else
    return (pos2 - pos3 + 1) - (result - budget + dist - 1) / dist;
}

int besthub(int R, int L, int X[], long long B)
{
  lim = L;
  n = R;
  for(int i = 1;i <= n; i++)
    v[i] = X[i - 1];
  for(int i = 1;i <= n; i++)
    sum[i] = sum[i - 1] + v[i];

  int result = 0;
  for(int i = 1;i <= n; i++) {
    int result2 = solve(i, B);
    result = MAX(result, result2);
  }
  return result;
}

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