Advertisement
Valkyrie006

Untitled

Oct 12th, 2021
39
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. ll n, X, Y;
  2. const ll MAXN = 1005;
  3. ll H[MAXN], pre[MAXN];
  4. ll dp[MAXN][MAXN];
  5.  
  6. ll cal(ll i, ll sum1)
  7. {
  8.     if (i == n)
  9.     {
  10.         return 0;
  11.     }
  12.     if (dp[i][sum1] != -1)
  13.     {
  14.         return dp[i][sum1];
  15.     }
  16.     if (sum1 + H[i] <= X)
  17.     {
  18.         dp[i][sum1] = max(dp[i][sum1], 1 + cal(i + 1, sum1 + H[i]));
  19.     }
  20.     if ((pre[i] - sum1) <= Y)
  21.     {
  22.         dp[i][sum1] = max(dp[i][sum1], 1 + cal(i + 1, sum1));
  23.     }
  24.     if (dp[i][sum1] == -1)
  25.     {
  26.         dp[i][sum1] = 0;
  27.     }
  28.     return dp[i][sum1];
  29. }
  30.  
  31. void solve()
  32. {
  33.     cin >> n >> X >> Y;
  34.     for (ll i = 0; i < n; i++)
  35.     {
  36.         cin >> H[i];
  37.     }
  38.     sort(H, H + n);
  39.     for (ll i = 0; i < n; i++)
  40.     {
  41.         pre[i] = H[i];
  42.         if (i > 0)
  43.             pre[i] += pre[i - 1];
  44.     }
  45.     memset(dp, -1, sizeof(dp));
  46.     cout << cal(0, 0) << endl;
  47.  
  48.     return;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement