Submission #1313596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313596		tsetsenbileg	Rice Hub (IOI11_ricehub)	C++20	0 / 100	0 ms	332 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pr = pair<int, int>;
#define pb push_back();
const int INF = 1e9+7;
int n;
ll k, l;



int besthub(int R, int L, int a[], long long B) {
  n = R; l = L; k = B;
  int res = 0;
  vector<int> pref(n);
  deque<int> lef, rig;
  int r = 0;
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    ll diff = (a[i] - a[max(0, i - 1)]);
    sum = (sum - rig.size() * diff + lef.size() * diff);
    lef.push_back(a[i]);
    if (!rig.empty()) {
      rig.pop_front();
      r++;
    }
    while (sum > k) {
      sum -= (a[i] - lef.front());
      lef.pop_front();
    }
    while (sum <= k && r < n) {
      if (sum + a[r] - a[i] > k) break;
      sum += a[r] - a[i];
      rig.push_back(a[r]);
      r++;
    }
    while (r < n) {
      ll b = lef.front();
      if (a[i] - b > a[r] - a[i]) {
        sum -= (a[i] - b);
        lef.pop_front();
        while (sum <= k && r < n) {
          if (sum + a[r] - a[i] > k) break;
          sum += a[r] - a[i];
          rig.push_back(a[r]);
          r++;
        }
      }
      else break;
    }
    res = max(res, (int)(lef.size() + rig.size()));
  }
  // for (auto i : lef) cout << i << ' ';
  // for (auto i : rig) cout << i << ' ';
  return res;
}

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