Submission #66727067

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
const int N=2e3+7;
const int mod=1e9+7;
const double eps=1e-9;
const double pi=    3.14159265358979323846;
using namespace std;  
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    op_set;

int32_t main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n,h,m;
    cin >> n >> h >> m;

    int dp[n+1][m+1];
    memset(dp,-1,sizeof(dp));

    dp[0][m]=h;

    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin >> a >> b;

        for(int j=0;j<=m;j++)
        {
            if(dp[i-1][j]>=a)
                dp[i][j]=std::max(dp[i-1][j]-a,dp[i][j]);
        }

        for(int j=b;j<=m;j++)
            dp[i][j-b]=std::max(dp[i-1][j],dp[i][j-b]);
    }

    int ans=0;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(dp[i][j]>=0)
                ans=i;
        }
    }

    cout << ans << "\n";
}

/*
Mar Gaye Ehsaas Meray, 
Chubay Wo Ilfaaz Teray, 
Tumne Dekha Tak Na Jaty Way, 
*/

Submission Info

Judge Result