Title:

website: http://codeforces.com/contest/1526/problem/C1

translate:
A person's initial health is 0 and there are n medicine bottles. Each medicine bottle has its own impact on health (a[i]). Now you can choose to drink or ignore each bottle of medicine from left to right, so as to find out how many bottles of medicine you can drink at most when the health value of the whole process is greater than or equal to 0

Idea:

When writing C1, because n is 2000, my first feeling is to write dp (because I really didn't think of another method qwq), so I began to push the transfer equation and write a dp of n2.

Also write down your thoughts (although you can't pass C2):
f [ i ] [ j ] f[i][j] f[i][j] records the maximum health value that can be obtained by drinking j bottles of medicine in the first I bottles of medicine. Then we can get an equation:
f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − 1 ] + a [ i ] ) f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i]) f[i][j]=max(f[i−1][j],f[i−1][j−1]+a[i])
(there is a special judgment to be made here, that is f [ i − 1 ] [ j ] f[i-1][j] f[i − 1][j] and f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i − 1][j − 1] cannot be less than 0 before transfer)
So for this dp equation, we just need to record f [ i ] [ j ] f[i][j] f[i][j] is the maximum j value of positive value (the number of bottles to drink)

dp Code:

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int mod=1e9+7;
const int N=2e3+5;
int n,ans,a[N];
ll f[N][N];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	    cin>>a[i];
	memset(f,-1,sizeof(f));
	if(n==1)
	{
		if(a[1]<0) cout<<0;
		else cout<<1;
		return;
	}
	f[1][0]=0,f[1][1]=a[1];
	for(int i=2;i<=n;i++)
	{
		f[i][0]=0;
		for(int j=1;j<=i;j++)
		{
			if(f[i-1][j]<0&&f[i-1][j-1]<0) f[i][j]=-1;  //Special judgment
			else f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i]);
			if(f[i][j]>=0) ans=max(ans,j);
		}
	}
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int __=1;
	//cin>>__;
	while(__--)
	    solve();
	return 0;
}

But when I think about two questions in a code happily, when I turn to C2, I see the data 2e5. I'm stupid. dp iron T of n2 has to think of a new solution 55555

Because this question asks for the maximum number of drugs to drink, we should consider how to get as high as possible in the case of taking the most drugs

Then we can try to be greedy:
For drugs with a [i] > = 0, we can drink them directly without much consideration
For those drugs with a [i] < 0, it can be considered in two cases:
1. If HP (health value) is > = 0, you can drink it directly
2. For those who drink HP < 0, we can consider whether it can help us achieve the highest life value under the condition of taking the most drugs
It is to compare the smallest drug of a[i] among the drugs currently drunk with it and judge whether this drug can be used to replace the smallest drug of a[i] (regret step)
For the operation in this case, we can use the priority queue to maintain the a[i] smallest medicine currently taken

Put the code:

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int mod=1e9+7;
const int N=2e5+5;
int n,ans,a[N];
ll hp;
void solve()
{
	priority_queue<ll,vector<ll>,greater<ll>> q;   //Keep the medicine you have taken in ascending order
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]>=0)  
		{
			ans++; hp+=a[i];
			q.push(a[i]);
		}
		else
		{
			if(hp+a[i]>=0)
			{
				ans++; hp+=a[i]; 
			    q.push(a[i]);
			}
			else if(!q.empty()&&a[i]>q.top())
			{
				int u=q.top(); q.pop();
				hp+=a[i]-u;
				q.push(a[i]);
			}
		}
	}
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int __=1;
	//cin>>__;
	while(__--)
	    solve();
	return 0;
}