here is my solution for thi problem from EL JUDGE ,
but the time limit is exceeds by 1 second ,
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct{
int m;
int s;
}rec;
bool compare(const rec& r1,const rec& r2)
{
return(r1.m + r1.s <= r2.m + r2.s);
}
int main()
{
int n,i,j;
int best[100000] ;
cin>>n;
i = 0;
vector<rec> v;
rec r;
while(i < n)
{
//cin>>r.m;
//cin>>r.s;
scanf("%d",&r.m);
scanf("%d",&r.s);
v.push_back(r);
i++;
}
for(i = 0;i<=n;i++)
best[i] = 4000000;
best[0] = 0;
sort(v.begin(),v.end(),compare);
int maxcount = 0;
for(i= 0; i < n;i++)
{
for(j = maxcount + 1; j > 0;j--)
{
if(v[i].s >= best[j -1] && (v[i].m + best[j -1] < best[j]))
{
best[j] = v[i].m + best[j -1];
if(j > maxcount) maxcount = j;
}
}
}
cout<<maxcount<<endl;
return 0;
}
need help to optimise this , the input length can be upto 100000