Submission #3043563

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

#define INF 1000000000000000000

typedef long long LL;


struct person{
  LL h;
  LL p;
  bool operator<(const struct person & right) const{
    return (h+p<right.h+right.p);
  }
};

int main(){
  int n;
  cin >> n;
  vector<struct person> san(n);
  vector<LL> dp(n+1,INF);
  dp[0]=0;
  for(int i=0;i<n;i++){
    cin >> san[i].h >> san[i].p;
  }
  sort(san.begin(),san.end());
  for(int i=0;i<n;i++){
    for(int j=n;j>0;j--){
      if(dp[j-1]<=san[i].h) dp[j]=min(dp[j],dp[j-1]+san[i].p);
    }
    // for(int j=0;j<=n;j++){
    //   cout << dp[j] << " ";
    // }
    // cout << endl;
  }
  for(int i=n;i>=0;i--){
    if(dp[i]!=INF){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

Submission Info

Judge Result