제출 #717905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717905		thimote75	쌀 창고 (IOI11_ricehub)	C++14	100 / 100	107 ms	1128 KiB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>
#define num long long
#define inf 1e18

using namespace std;

vector<int> X;

int _besthub (int R, int L, num B) {
  int mxCount = 0;

  int left  = 0;
  int right = 0;
  num cost  = 0;
  
  for (int idx = 0; idx < R; idx ++) {
      //printf("a%d: %d %d [%lld]\n", idx, left, right, cost);
    while (cost > B) {
      if (left == right) {
        left = idx;
        right = idx;
        cost = 0;
        break;
      }

      num dlc = X[left ] - X[idx];
      num drc = X[right] - X[idx];

      cost -= max(dlc, drc);
      if (dlc >= drc) left ++;
      else right --;
    }
      //printf("b%d: %d %d [%lld]\n", idx, left, right, cost);

    while (right != R - 1) {
      //printf("bs%lld %d %d", cost, X[right + 1] - X[idx], X[right + 1] - X[idx] - (X[idx] - X[left]));
      if (X[right + 1] - X[idx] + cost <= B) {
        //printf("br\n");
        cost += X[right + 1] - X[idx];
        right ++;
      } else if (X[right + 1] - X[idx] < X[idx] - X[left]) {
        //printf("bl\n");
        cost += X[right + 1] - X[idx] - (X[idx] - X[left]);
        right ++;
        left ++;
      } else break ;
      //printf("be%lld %d %d\n", cost, X[right + 1] - X[idx], X[right + 1] - X[idx] - (X[idx] - X[left]));
    }
      //printf("\nc%d: %d %d [%lld]\n", idx, left, right, cost);

    if (idx + 1 != R) {
      num delta = X[idx + 1] - X[idx];

      cost += delta * (idx - left  + 1);
      cost -= delta * (right - idx);
    }
      //printf("d%d: %d %d [%lld]\n", idx, left, right, cost);
    mxCount = max(mxCount, right - left + 1);
  }

  return mxCount;
}

int besthubnaive(int R, int L, int X[], num B)
{
    int mxCount = 0;
 
    for (int idx = 0; idx < R; idx ++) {
      int left  = idx - 1;
      int right = idx + 1;
 
      num cost  = 0;
      int count = 1;
      while (true) {
        int dcl = left == -1 ? inf : abs(X[left]  - X[idx]);
        int dcr = right == R ? inf : abs(X[right] - X[idx]);
 
        if (min(dcl, dcr) + cost > B) break ;
        cost  += min(dcl, dcr);
        count ++;
        
        if (dcl <= dcr) left --;
        else right ++;
      }

      mxCount = max(count, mxCount);
    }
 
    return mxCount;
}
int besthub(int R, int L, int _X[], num B)
{
  X.resize(R);
  for (int i = 0; i < R; i ++)
    X[i] = _X[i];
  
  if (R <= 5000) return besthubnaive(R, L, _X, B);
  int res = _besthub(R, L, B);
  return res;

  /*if (res != besthubnaive(R, L, _X, B)) {
    printf("%d %d %lld\n", R, L, B);
    for (int u : X)
      printf("%d\n", u);
    printf("%d\n", besthubnaive(R, L, _X, B));
    exit(1);
  }

  exit(0);*/
}

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