Submission #2247117

---

Source Code Expand

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
typedef pair<LL, LL> P;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x)      (x).begin(),(x).end()
# define UNIQ(c)     (c).erase(unique(ALL((c))),(c).end())
# define mp          make_pair
# define eb          emplace_back
# define FOR(i,a,b)  for(int i=(a);i<(b);i++)
# define RFOR(i,a,b) for(int i=(a);i>=(b);i--)
# define REP(i,n)    FOR(i,0,n)
# define INIT        std::ios::sync_with_stdio(false);std::cin.tie(0)

int h[5050], p[5050], a[5050];
int n;
LL dp[5050];
int compare(int k1, int k2) {
	return h[k1] + p[k1] < h[k2] + p[k2];
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> h[i] >> p[i];
	}
	for (int i = 1; i <= n; i++) a[i] = i;
	sort(a + 1, a + n + 1, compare);
	REP(i, 5050)dp[i] = HLINF;
	dp[0] = 0;
	for (int i = 1; i <= n; i++)for (int j = n; j >= 0; j--)if (dp[j] <= h[a[i]]) dp[j + 1] = min(dp[j + 1], dp[j] + p[a[i]]);
	int ans = 0;
	for (int i = 1; i <= n; i++) if (dp[i] < HLINF) ans = i;
	cout << ans << endl;
}

Submission Info

Judge Result