Submission #66740590

---

Source Code Expand

#if __has_include("pch.hpp")
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <atcoder/segtree>
#endif
using namespace std;
//using namespace atcoder;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937_64 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//ld rand(ld a, ld b) {uniform_real_distribution<ld> uni(a, b); return uni(mt_rand);}
//const ld PI=3.141592653589793238462643383279;
const int mxN=1e6+50000;
const int mod=1e9+7;
const int mxlogN=19;
const ll inf=1e18;
const int iinf=1e9;
const int K=60;
int dp[3002][3002];
int a[mxN], b[mxN];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, h, m; cin >> n >> h >> m;
    for(int i=0; i<n; i++) cin >> a[i] >> b[i];
    for(int i=0; i<=n; i++) for(int j=0; j<=h; j++) dp[i][j]=m+1;
    dp[0][0]=0;
    int ans=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<=h; j++)
        {
            if(dp[i][j]>m) continue;
            int k=dp[i][j];
            if(j+a[i]<=h) dp[i+1][j+a[i]]=min(dp[i+1][j+a[i]],k);
            if(k+b[i]<=m) dp[i+1][j]=min(dp[i+1][j],k+b[i]);
        }
        int ok=0;
        for(int j=0; j<=h; j++)
        {
            if(dp[i+1][j]<=m) ok=1;
        }
        if(ok) ans=i+1;
        else break;
    }
    cout << ans << "\n";
}

Submission Info

Judge Result