Submission #2313253

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=5010;
int a[N],b[N],v[N],id[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline bool cmp(const int &x,const int &y) {return b[x]+a[x]<b[y]+a[y];}
int main() {
    int n,tp=0;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),b[i]=gi(),id[i]=i;
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++) {
	int t=id[i];
	if(v[tp]<=a[t]) ++tp,v[tp]=v[tp-1]+b[t];
	for(int j=tp;~j;j--)
	    if(v[j]<=a[t]) v[j+1]=min(v[j+1],v[j]+b[t]);
	if(v[tp+1]) ++tp;
    }
    cout<<tp;
    return 0;
}

Submission Info

Judge Result