Submission

[PPPPPPPP][PPPPPPPP][PPPPPPPPP]

Score: 100

User: Nathako9n

Problemset: 06.Happiness

Language: cpp

Time: 0.025 second

Submitted On: 2025-03-31 23:22:59

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> happiness(n);
    for (int i = 0; i < n; i++){
        cin >> happiness[i];
    }

    long long sum = 0;
    int coun = 0;
    // min-heap: smallest element (most negative) will be at the top
    priority_queue<int, vector<int>, greater<int>> negatives;

    for (int i = 0; i < n; i++){
        int val = happiness[i];
        if(val >= 0){
            // positive values always help (or do not harm)
            sum += val;
            coun++;
        } else {
            // try to include a negative value
            sum += val;
            coun++;
            negatives.push(val);
            // if sum goes negative, remove the most harmful negative
            if(sum < 0){
                sum -= negatives.top(); // remove the negative effect
                negatives.pop();
                coun--;
            }
        }
    }

    cout << coun;
    return 0;
}

/*

6
7 -2 -6 -5 0 1

*/