fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. #define int long long
  5. #define INTMAX 1e15+5
  6. #define N 1000005
  7.  
  8. int min(int a, int b) { if (a > b) swap(a, b); return a;}
  9.  
  10. int dp[100005][100];
  11.  
  12. int solveDp(int val, int index, int item[][2], int n) {
  13.        if (val <= 0)    return 0;
  14.        if (index == n)  return INTMAX;
  15.        if (dp[val][index] != -1)       return dp[val][index];
  16.  
  17.        dp[val][index] = min(item[index][0] + solveDp(val - item[index][1], index + 1, item, n),
  18.                             solveDp(val, index + 1, item, n));
  19.        return dp[val][index];
  20. }
  21.  
  22. int calc(int cap, int n, int item[][2]) {
  23.        for (int i = 100000; i >= 0; i--) {
  24.               if (solveDp(i, 0, item, n) <= cap)       return i;
  25.        }
  26.        return 0;
  27. }
  28.  
  29.  
  30. void solve() {
  31.        int n, w;      cin >> n >> w;
  32.        int item[n][2];
  33.        memset(dp, -1, sizeof(dp));
  34.        for (int i = 0; i < n; i++) cin >> item[i][0] >> item[i][1];
  35.        cout << calc(w, n, item);
  36. }
  37.  
  38.  
  39.  
  40.  
  41. signed main()
  42. {
  43.        solve();
  44. }
Runtime error #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/B0Joub
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!