Submission #998896

#	Time	Username	Problem	Language	Result	Execution time	Memory
998896		Mr_Husanboy	Rice Hub (IOI11_ricehub)	C++17	100 / 100	30 ms	6484 KiB

ricehub

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

using namespace std;
#define ll long long

template<typename T>
int len(T &a){return a.size();}

int besthub(int n, int lim, int a[], long long cost)
{
  int ans = 0;

  multiset<int> lef, rig;
  ll sl = 0, sr = 0;

  ll mon = 0;

  auto add = [&](int x){
    if(lef.empty() || *lef.rbegin() >= x){
      lef.insert(x);
      sl += x;
      if(len(lef) - 1 >= len(rig) + 1){
        int m = *lef.rbegin();
        lef.erase(lef.find(m));
        sl -= m;
        rig.insert(m);
        sr += m;
      }
    }else{
      rig.insert(x);
      sr += x;
      if(len(rig) > len(lef)){
        ll m = *rig.begin();
        rig.erase(rig.begin());
        sr -= m;
        lef.insert(m);
        sl += m;
      } 
    }
    if(lef.empty()) mon = 0;
    else{
      ll m = *lef.rbegin();
      mon = m * len(lef) - sl + sr - m * len(rig);
    }
  };

  auto rem = [&](int x){
    if(x > *lef.rbegin()){
      rig.erase(rig.find(x));
      sr -= x;
      if(len(lef) - 1 >= len(rig) + 1){
        int m = *lef.rbegin();
        lef.erase(lef.find(m));
        sl -= m;
        rig.erase(m);
        sr += m;
      }
    }else{
      lef.erase(lef.find(x));
      sl -= x;
      if(len(rig) > len(lef)){
        ll m = *rig.begin();
        rig.erase(rig.begin());
        sr -= m;
        lef.insert(m);
        sl += m;
      } 
    }
    if(lef.empty()) mon = 0;
    else{
      ll m = *lef.rbegin();
      mon = m * len(lef) - sl + sr - m * len(rig);
    }
  };

  for(int l = 0, r = 0; r < n; r ++){
    add(a[r]);
    while(mon > cost){
      rem(a[l]);
      l ++;
    }
    if(mon <= cost) ans = max(ans, r - l + 1);
  }
  return ans;
}

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