Submission #2976910

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = (1LL << 60);

int main(){
	int N;
	while(cin >> N){
		vector<pair<int,int>> vp(N);
		for(auto& t : vp) cin >> t.first >> t.second;
		sort(vp.begin(), vp.end(),
		     [](const pair<int,int>& a, const pair<int, int>& b){
				return a.first + a.second < b.first + b.second;
		     }
		);
		vector<long long> dp(N+1, INF);
		dp[0] = 0;
		for(int i=0;i<N;i++){
			for(int j=i;j>=0;j--){
				if(dp[j] <= vp[i].first){
					dp[j+1] = min(dp[j+1], dp[j] + vp[i].second);
				}
			}
		}
		for(int i=N;i>=0;i--){
			if(dp[i] != INF){
				cout << i << endl;
				break;
			}
		}
	}
}

Submission Info

Judge Result