fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. void fast_io()
  6. {
  7.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  8. }
  9.  
  10. int main()
  11. {
  12.     fast_io();
  13.     int m, n;
  14.     cin >> n >> m;
  15.     int p[n+1] = {0};
  16.     int w[n+1] = {0};
  17.     int v[n+1][m+1];
  18.  
  19.     for (int i = 1; i < n+1; i++){
  20.         cin >> w[i] >> p[i];
  21.     }
  22.  
  23.     for (int i = 0; i < n+1; i++){
  24.         for (int j = 0; j < m+1; j++){
  25.             v[i][j] = 0;
  26.         }
  27.     }
  28.  
  29.     for (int i = 1; i < n+1; i++){
  30.         for (int j = 1; j < m+1; j++){
  31.             if (j-w[i] >= 0){
  32.                 v[i][j] = max(v[i-1][j], v[i-1][j-w[i]]+p[i]);
  33.             }else{
  34.                 v[i][j] = v[i-1][j];
  35.             }
  36.         }
  37.     }
  38.     int num = v[n][m];
  39.     int results[n+1] = {0};
  40.     for (int i = n; i >= 1; i--){
  41.         for (int j = m; j >= 1; j--){
  42.             if (v[i-1][j] == num){
  43.                 break;
  44.             }
  45.             if (j == 1){
  46.                 num -= p[i];
  47.                 results[i] = 1;
  48.             }
  49.         }
  50.     }
  51.     int sum = 0;
  52.     for (int i = 0; i < n+1; i++){
  53.         if (results[i] == 0){continue;}
  54.         sum += p[i];
  55.     }
  56.     cout << sum << endl;
  57. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
6 15
6 5
5 6
6 4
6 6
3 5
7 2
stdout
copy 
17
https://ideone.com/Wd4igj
language:
C++ (gcc 8.3)
created:
8 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!