제출 #168928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168928		AlexLuchianov	쌀 창고 (IOI11_ricehub)	C++14	0 / 100	405 ms	3064 KiB

ricehub

#include "ricehub.h"

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 v[1 + nmax], n;
ll 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;
}

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

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

  return result + result2 <= budget;
}

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

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

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

  return (pos2 - pos3 + 1) - 1 - (result - budget + 1) / dist;
}

int besthub(int R, int L, int X[], long long B)
{
  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: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32