oj.uz

Submission #998895

# Submission time Handle Problem Language Result Execution time Memory
998895 2024-06-14T19:27:09 Z Mr_Husanboy Rice Hub (IOI11_ricehub) C++17
17 / 100
 30 ms 6544 KB 
#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.erase(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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Runtime error 1 ms 448 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 0 ms 348 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 568 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 29 ms 6396 KB Output is correct
4 Correct 30 ms 6544 KB Output is correct
5 Runtime error 4 ms 1092 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -