Submission #1005199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005199		Gray	Rice Hub (IOI11_ricehub)	C++17	100 / 100	36 ms	9176 KiB

ricehub

#include "ricehub.h"
#include <iostream>
#include <set>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;

ll n;

int besthub(int R, int L, int X[], long long B)
{
  n=R;
  vector<ll> a(n);
  for (ll i=0; i<n; i++){
    a[i]=X[i];
  }
  ll l=0, r=0;
  ll ans=1, lsum=0, rsum=a[0];
  multiset<ll> left;
  multiset<ll> right;
  right.insert(a[0]);
  while (r<n){
    // cout << l << " " << r << endl;
    ll cmed = (*right.begin());
    if ((ll)(cmed*left.size()-lsum+rsum-cmed*(right.size()))<=(ll)B){
      ans=max(ans, r-l+1);
      r++;
      ll nwl=r-l+1;
      if (r==n) break;
      if (left.empty() or a[r]>(*left.begin())){
        right.insert(a[r]);
        rsum+=a[r];
      }else{
        left.insert(a[r]);
        lsum+=a[r];
      }
      while ((ll)right.size()>nwl-nwl/2){
        rsum-=*right.begin();
        lsum+=*right.begin();
        left.insert(*right.begin());
        right.erase(right.begin());
      }
      while (left.size()>right.size()){
        lsum-=*left.rbegin();
        rsum+=*left.rbegin();
        right.insert(*left.rbegin());
        left.erase(left.find(*left.rbegin()));
      }
    }else{
      // cout << "H" << endl;
      if (left.find(a[l])!=left.end()){
        lsum-=a[l];
        left.erase(left.find(a[l]));
      }else{
        rsum-=a[l];
        right.erase(right.find(a[l]));
      }
      l++;
      ll nwl=r-l+1; 
      while ((ll)right.size()>nwl-nwl/2){
        rsum-=*right.begin();
        lsum+=*right.begin();
        left.insert(*right.begin());
        right.erase(right.begin());
      }
      while (left.size()>right.size()){
        lsum-=*left.rbegin();
        rsum+=*left.rbegin();
        right.insert(*left.rbegin());
        left.erase(left.find(*left.rbegin()));
      }
    }
  }
  return ans;
}

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