Codeforces - 1526C1＆＆C2 - Potions

Codeforces - C1&&C2 - Potions

There are n potions in a line, with potion 1 on the far left and potion n on the far right. Each potion will increase your health by ai when drunk. ai can be negative, meaning that potion will decrease will health.

You start with 0 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?

Input

The first line contains a single integer n (1≤n≤200000) — the number of potions.

The next line contains n integers a1, a2, … ,an (−10^9≤ai≤109) which represent the change in health after drinking that potion.

Output

Output a single integer, the maximum number of potions you can drink without your health becoming negative.

Example

input

6
4 -4 1 -3 1 -3

output

5

Problem analysis

This question means yes n Bottle medicine , You will recover after eating a[i] Hit points or reduce a[i] Point health , You eat from left to right （ You can also choose not to eat ）, Ask how many bottles of medicine you can take when your health value is not negative .

because c1 and c2 Only data size differences , I'll just follow c2 To write , This question can be directly written greedily , Just ignore those small potions .

We can prepare a small root pile , Insert the potion into the small root pile from left to right , When the sum of small root piles is negative , Just pop up the smallest element , Until the sum is not negative , In this process, maintain the maximum amount of water taken . Every insert and eject is logn, So the total complexity is nlogn.

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
int n, m;


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;

    int n;
    cin >> n;
    vector<int>v(n);
    priority_queue<int,vector<int>,greater<int>>que;
    int res = 0,ans=0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        que.push(v[i]);
        res += v[i];
        while (res < 0)
        {
            res -= que.top();
            que.pop();
        }
        ans = max(ans, (ll)que.size());
    }
    cout << ans << endl;
    return 0;
}