Submission

Score: 20

User: pxsit

Problemset: 06.Happiness

Language: cpp

Time: 0.042 second

Submitted On: 2025-03-31 07:58:28

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long

void solve(){
    int n; cin >> n;
    ll arr[n+1]; arr[0]=0;
    ll dp[n+1]; dp[0]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        dp[i]=arr[i]+dp[i-1];
        if(arr[i]<0) pq.emplace(arr[i],i);
    }
    // cout << "PASS";
    int cnt = 0;
    ll sum = 0;
    while(!pq.empty()){
        bool valid = true;
        for(int i = 1; i <= n; i++){
            if(dp[i]+sum<0){
                valid = false;
                break;
            }
        }if(valid) break;
        else{
            cnt++;
            sum -= pq.top().first;
            pq.pop();
        }
    }cout << n-cnt;
    return;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}