Submission #1192811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192811		Hamed_Ghaffari	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	1096 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define SZ(x) int(x.size())

int besthub(int R, int L, int X[], ll B) {
  deque<int> dql, dqr;
  ll suml=0, sumr=0;
  auto fix = [&]() -> void {
    while(SZ(dqr)>SZ(dql)) {
      sumr -= dqr.front();
      dql.push_back(dqr.front());
      suml += dqr.front();
      dqr.pop_front();
    }
    while(SZ(dql)-1>=SZ(dqr)+1) {
      suml -= dql.back();
      dqr.push_front(dql.back());
      sumr += dql.back();
      dql.pop_back();
    }
  };
  auto ins = [&](int x) -> void {
    dqr.push_back(x);
    sumr += x;
    fix();
  };
  auto er = [&]() -> void { 
    suml -= dql.front();
    dql.pop_front();
    fix();
  };
  auto cost = [&]() -> ll {
    return 1ll*SZ(dql)*dql.back() - suml + (sumr - 1ll*SZ(dqr)*dql.back());
  };
  int ans = 0;
  int l=0;
  for(int r=0; r<R; r++) {
    ins(X[r]);
    while(cost()>B) er(), l++;
    ans = max(ans, r-l+1);
  }
  return ans;
}

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