Submission

[-SSSSSSSSS]

Score: 0

User: Dormon

Problemset: 02.Forbidden Boss Room

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-31 10:49:15

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;
#define fr first
#define se second

struct Fenwick{
    vector<int> fw;
    int n;
    Fenwick(int sz) : n(sz + 1) {
        fw.resize(sz + 1);
    }

    void upd(int i, int val){
        for (;i < n;i+=i&-i)
            fw[i] += val;
    }
    int qry(int i){
        int res = 0;
        for (;i;i-=i&-i)
            res += fw[i];
        return res;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n + 1);
    vector<pair<int, int>> neg;
    Fenwick tree(n + 1);
    int ans = 0;
    for (int i = 1;i <= n;i++){
        cin >> v[i];
        if (v[i] >= 0){
            ans++;
            tree.upd(i, v[i]);
        }
        else 
            neg.push_back({-v[i], i});
    }
    sort(neg.begin(), neg.end());
    for (auto [d, idx]:neg){
        if (tree.qry(idx) >= d){
            tree.upd(idx, -d);
            ans++;
        }
    }
    cout << ans << "\n";
}