Submission #66761267

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <time.h>
#include <sstream>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string.h>
#include <assert.h>
#include <iomanip>
#include <bitset>
#include <functional>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ull unsigned long long
#define int long long
#define F first
#define S second
#define nl "\n"
#define sortv(v) sort(v.begin(),v.end())
#define rsortv(v) sort(v.rbegin(),v.rend())
#define all(v) v.begin(),v.end()
#define div 1000000007
#define div2 998244353
#define PI 3.141592653589793
#define inf 1000000000000000000LL
#define blk 320
#define pb push_back


void solve()
{
    int n,h,m;cin>>n>>h>>m;
    int a[n + 1], b[n + 1];
    for (int i = 1; i <= n; i++)
        cin>>a[i]>>b[i];
    
    int dp[n + 1][h + 1];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= h; j++)
        {
            if (i == 0)
                dp[i][j] = m;
            else
               dp[i][j] = -1;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= h; j++)
        {
            if (j - a[i] >= 0)
                dp[i][j] = dp[i - 1][j - a[i]];
            
            if (dp[i - 1][j] - b[i] >= 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j] - b[i]);
        }
    }

    int ans = 0;
    for (int i = n; i > 0; i--)
    {
        if (dp[i][h] >= 0)
        {
            ans = i;
            break;
        }
    }
    cout<<ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Submission Info

Judge Result