Language: C++

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const int N = 5010;
const int INF = 1e18;
int dp[N][N], dp2[N][N];

int main() {
    int n;
    cin >> n;
    vector<PL> a(n);
    REP(i,n) cin >> a[i].first >> a[i].second;
    // REP(i,n) a[i].first = 0, a[i].second = 0;
    sort(ALL(a));
    VL h(n), p(n);
    REP(i,n){
        h[i] = a[i].first;
        p[i] = a[i].second;
    }
    REP(i,N) REP(j,N) dp[i][j] = dp2[i][j] = INF;
    dp[0][0] = 0;
    REP(i,n-1){
        REP(j,i+1){
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
            int k = i+1;
            // k = upper_bound(ALL(h), dp[i][j] + p[i]) - h.begin();
            // k--;
            int ok = n, ng = i;
            while (ok - ng > 1){
                int mi = (ok + ng) / 2;
                if (dp[i][j] + p[i] <= h[mi]) ok = mi;
                else ng = mi;
            }
            // while (k < n && dp[i][j] + p[i] > h[k]) k++;
            k = ok;
            dp[k][j+1] = min(dp[k][j+1], dp[i][j] + p[i]);
        }
    }
    dp2[n][0] = 0;
    FORR(i,n-1,0){
        REP(j,n+1){
            dp2[i][j] = min(dp2[i][j], dp2[i+1][j]);
            dp2[i][j+1] = min(dp2[i][j+1], dp2[i+1][j] + p[i]);
        }
    }
    // cout << "hes" << endl;
    int ans = 0;
    REP(i,n){
        int k = n;
        REP(j,n){
            while (k >= 0 && dp[i][j] + dp2[i+1][k] > h[i]) k--;
            ans = max(ans, j + k);
        }
    }

    // REP(i,n+1){
    //     REP(j,n+1){
    //         cout << dp2[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    cout << ans + 1 << endl;
    return 0;
}





Compiler output:
a.cc:30:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   30 | const int INF = 1e18;
      |                 ^~~~
a.cc: In function 'int main()':
a.cc:61:29: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)'
   61 |             dp[k][j+1] = min(dp[k][j+1], dp[i][j] + p[i]);
      |                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:61:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   61 |             dp[k][j+1] = min(dp[k][j+1], dp[i][j] + p[i]);
      |                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:13:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:61:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   61 |             dp[k][j+1] = min(dp[k][j+1], dp[i][j] + p[i]);
      |                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:68:30: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)'
   68 |             dp2[i][j+1] = min(dp2[i][j+1], dp2[i+1][j] + p[i]);
      |                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:68:30: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   68 |             dp2[i][j+1] = min(dp2[i][j+1], dp2[i+1][j] + p[i]);
      |                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:68:30: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   68 |             dp2[i][j+1] = min(dp2[i][j+1], dp2[i+1][j] + p[i]);
      |                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~