제출 #895766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895766		vjudge1	Rice Hub (IOI11_ricehub)	C++17	100 / 100	12 ms	4444 KiB

ricehub

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

using namespace std;
#define ll long long

int besthub(int R, int L, int X[], long long B)
{


  vector<ll> a(R + 1);

  for (int i = 1; i <= R; i++) {
    a[i] = X[i - 1];
    a[i] += a[i - 1];
  }

  int ans = 0;

  int ptr = 1;
  for (int i = 1; i <= R; i++) {
    ptr = max(ptr, i);

    while (ptr + 1 <= R) {

      ll nmid = i + ((ptr + 1) - i + 1) / 2;

      ll tot = (a[ptr + 1] - a[nmid]) - ((ll)(ptr + 1) - nmid) * X[nmid - 1];

      tot += (((ll)(nmid - i + 1))) * X[nmid - 1] - (a[nmid] - a[i - 1]);

      // cout << i << " -> " << ptr + 1 << " takes " << tot << endl;

      if (tot > B) break;
      ptr++;

    }

    ans = max(ans, ptr - i + 1);

    // cout << i << " : " << ptr << endl;

  }

  return ans;

}

// int main() {

//   int xx[5] = {1, 2, 10, 12, 14};
//   cout << besthub(5, 20, xx, 6) << endl;

// }

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