fork download
copy 
  1. /*
  2.  *
  3.  */
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define el     '\n'
  7. const int mod = 1000000000 + 7, OO = 0x3f3f3f3f;
  8. const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
  9. const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
  10. const char di[] = {'U', 'R', 'L', 'D'};
  11. const int N = 1000 + 5, M = 1e5 + 5;
  12. int n, m;
  13. vector<int> w, v;
  14. int64_t dp[N][M];
  15.  
  16. int clc(int i, int sum) {
  17.     if (sum > m) return -1e9;
  18.     if (i == n) return 0;
  19.  
  20.     int64_t &ret = dp[i][sum];
  21.  
  22.     if (~ret) return ret;
  23.  
  24.     int64_t l = clc(i + 1, sum);
  25.     int64_t t =(v[i] + clc(i + 1, sum + w[i]));
  26.  
  27.     ret = max(l, t);
  28.     return ret;
  29. }
  30.  
  31. void solve() {
  32.     cin >> n >> m;
  33.     memset(dp, -1, sizeof dp);
  34.     for (int i = 0; i < n; ++i) {
  35.         int x;
  36.         cin >> x;
  37.         w.push_back(x);
  38.         cin >> x;
  39.         v.push_back(x);
  40.     }
  41.  
  42.     cout << clc(0, 0) << el;
  43.  
  44. }
  45.  
  46. int32_t main() {
  47.     ios_base::sync_with_stdio(false);
  48.     cout.tie(nullptr), cin.tie(nullptr);
  49.  
  50.     // if(fopen("in.txt", "r")){
  51.     //     freopen("in.txt", "r", stdin);
  52.     //     freopen("out.txt", "w", stdout);
  53.     // }
  54.  
  55.     int tt = 1;
  56.     //cin >> tt;
  57.     while (tt--) {
  58.         solve();
  59.     }
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.19s 788656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/faoRjI
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!