Submission #717886

#	Time	Username	Problem	Language	Result	Execution time	Memory
717886		thimote75	Rice Hub (IOI11_ricehub)	C++14	0 / 100	2 ms	468 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 ++) {
    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 --;
    }

    while (right != R - 1) {
      if (X[right + 1] - X[idx] + cost <= B) {
        cost += X[right + 1] - X[idx];
        right ++;
      } else if (X[right + 1] - X[idx]
              - (X[idx] - X[left])
              + cost <= B) {
        right ++;
        left ++;
        cost += X[right + 1] - X[idx] - (X[idx] - X[left]);
      } else break ;
    }

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

      cost += delta * (idx - left  + 1);
      cost -= delta * (right - idx + 1);
    }

    mxCount = max(mxCount, right - left + 1);
  }

  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];
  return _besthub(R, L, B);
}

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