HackerEarth Zero subarray problem solution

In this HackerEarth Zero subarray problem solution, we have given an array A of N elements. You can apply the given operations on array A.

Type 1: Choose an index i (1 ≤ i ≤ N) and set A[i] = A[i] – 1.

Type 2: Choose an index i (1 ≤ i ≤ N) and set A[i] = 0.

Find the maximum length subarray in array A where all the elements in the subarray is 0 by using at most X operations of Type 1 and Y operations of Type 2.

HackerEarth Zero subarray problem solution.

#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n, x, y;
int a[100005];

bool check(int l){
    multiset<int>p,q;
    int sum = 0;

    for(int i = 1 ; i <= l ; i++){
        p.insert(a[i]);
        if((int)p.size() > y){
            int value = *(p.begin());
            sum += value;
            q.insert(value);
            p.erase(p.begin());
        }
    }

    if(sum <= x) return true;

    for(int i = l + 1 ; i <= n ; i++){
        p.insert(a[i]);
        if((int)p.size() > y){
            int value = *(p.begin());
            sum += value;
            q.insert(value);
            p.erase(p.begin());
        }

        multiset<int>::iterator it = q.find(a[i - l]);
        if(it != q.end()){
            q.erase(it);
            sum -= a[i - l];
        }
        else{
            it = q.end();
            it--;

            int value = *it;
            sum -= value;
            q.erase(it);
            p.insert(value);
            p.erase(p.find(a[i-l]));
        }

        if(sum <= x) return true;
    }

    return (sum <= x);
}

void solve(){
    cin >> n >> x >> y;
    assert(1 <= n and n <= 100000);
    assert(0 <= x and x <= 100000000000000);
    assert(0 <= y and y <= 1000000000);
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
        assert(0 <= a[i] and a[i] <= 1000000000);
    }

    int ans = min(y, n);
    int s = min(y, n) + 1;
    int e = n;
    while(s <= e){
        int m = (s + e)/2;
        if(check(m)){
            ans = m;
            s = m + 1;
        }
        else{
            e = m - 1;
        }
    }
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    assert(1 <= t and t <= 5);
    while(t--){
        solve();
    }
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;
int n, a[MAX_N], y;
ll x;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> x >> y;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        multiset<int> bigs, smalls;
        int ptr = 0, ans = 0;
        ll sum = 0;
        for (int i = 0; i < n; ++i) {
            bigs.insert(a[i]);
            if (bigs.size() > y) {
                smalls.insert(*bigs.begin());
                sum += *bigs.begin();
                bigs.erase(bigs.begin());
            }
            while (sum > x) {
                if (bigs.find(a[ptr]) != bigs.end()) {
                    bigs.erase(bigs.find(a[ptr]));
                    if (!smalls.empty()) {
                        bigs.insert(*smalls.rbegin());
                        sum -= *smalls.rbegin();
                        smalls.erase(--smalls.end());
                    }
                }
                else {
                    sum -= a[ptr];
                    smalls.erase(smalls.find(a[ptr]));
                }
                ++ptr;
            }
            ans = max(ans, i - ptr + 1);
        }
        cout << ans << 'n';
    }
}

coding problems solutions