fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int max(int a, int b){
  5.     if (a > b) return a;
  6.     return b;
  7. }
  8.  
  9. int main() {
  10.     int t;
  11.     cin >> t;
  12.     for (int i = 0; i < t; i++){
  13.         int n, p;
  14.         cin >> n >> p;
  15.         int s[1000], v[1000];
  16.         int A[1000][10001] = {0};
  17.         for (int j = 0; j < n; j++) {
  18.             cin >> s[j] >> v[j];
  19.         }
  20.         for (int j = 0; j < n; j++){
  21.             for (int k = 0; k <= p; k++){
  22.                 if (j == 0) {
  23.                     if (k >= s[j]) A[j][k] = v[j];
  24.                     else A[j][k] = 0;
  25.                 } else {
  26.                     if (k >= s[j])
  27.                         A[j][k] = max(A[j-1][k], A[j-1][k - s[j]] + v[j]);
  28.                     else
  29.                         A[j][k] = A[j-1][k];
  30.                 }
  31.             }
  32.         }
  33.  
  34.         cout << A[n-1][p];
  35.     }
  36.     return 0;
  37. }
Success #stdin #stdout 0.01s 42616KB
comments (?)
stdin
copy 
1
4 10
3 5
8 16
3 5
4 7
stdout
copy 
17
https://ideone.com/MZ7Qsq
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!