Submission #1036212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036212		HappyCapybara	Rice Hub (IOI11_ricehub)	C++17	49 / 100	10 ms	2684 KiB

ricehub

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

#define ll long long

int besthub(int R, int L, int X[], ll B){
  queue<ll> l, r;
  for (int i=0; i<R; i++) r.push(X[i]);

  int bsf = 0, curl = 0, curr = 0, i = 0;
  ll k = 0;
  while (true){
    //cout << k << " " << r.front() << " " << X[i] << " " << B << "\n";
    while (!r.empty() && ((k+(r.front()-(ll) X[i])) <= B)){
      //cout << "a\n";
      k += r.front()- (ll) X[i];
      l.push(r.front());
      r.pop();
      curr++;
    }
    while (!l.empty() && !r.empty() && curl && (r.front()-X[i]) < (X[i]-l.front())){
      //cout << "b\n";
      k += r.front()+l.front()-2ll* (ll) X[i];
      l.pop();
      l.push(r.front());
      r.pop();
      curl--;
      curr++;
    }
    //cout << k << " " << r.front() << " " << X[i] << " " << B << "\n";
    while (!r.empty() && ((k+(r.front()-(ll) X[i])) <= B)){
      //cout << "a\n";
      k += r.front()- (ll) X[i];
      l.push(r.front());
      r.pop();
      curr++;
    }
    if (k <= B) bsf = max(bsf, curl+curr);
    //cout << i << " " << curl << " " << curr << " " << k << " " << bsf << "\n";
    i++;
    if (i == R) break;
    curl++; curr--;
    k += (ll) (curl-curr) * (ll) (X[i]-X[i-1]);
  }

  return bsf;
}

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