fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int nax = 1e+3, W = 1e+5;
  5. int dp[nax][W][2]; 
  6.  
  7. int n, max_weight;
  8. vector<vector<int>>a;
  9.  
  10.  
  11. int dfs(int i, int j, int odd){
  12.     // If the current item is out of the list or weight that I have > W.
  13.     // Return 0 as I can't take anything.
  14.     if(i >= n || j > max_weight){
  15.         return 0;
  16.     }
  17.     int ans = 0;
  18.     if(a[i][2] == 0){
  19.         // We have a red product
  20.         // Either we can take this or reject it
  21.  
  22.         // Take it
  23.         ans = max(ans, a[i][0] + dfs(i + 1, j + a[i][1], odd));
  24.  
  25.         // Not take it
  26.         ans = max(ans, dfs(i + 1, j, odd));
  27.     }else{
  28.         // We have a blue product
  29.  
  30.         // Either take it
  31.         ans = max(ans, a[i][0] + dfs(i + 1, j + a[i][1], (odd + 1) % 2));
  32.  
  33.         // Not take it
  34.         ans = max(ans, dfs(i + 1, j + a[i][1], odd));
  35.     }
  36.  
  37.     return dp[i][j][odd] = ans;
  38. }
  39.  
  40. void test_case(){
  41.      cin >> n >> max_weight;
  42.      a = vector<vector<int>>(n, vector<int>(3));
  43.      for(int i = 0; i < n; i++){
  44.         cin >> a[i][0] >> a[i][1] >> a[i][2]; 
  45.      }
  46.      memset(dp, -1, sizeof(dp)); 
  47.      dfs(0, 0, 0);
  48.  
  49.      // Now take all the maximum over all the values [i, j] where type == 0. 
  50.     int ans = 0;
  51.     for(int i = 0; i < n; i++){
  52.         for(int w = 0; w <= max_weight; w++){
  53.             ans = max(ans, dp[i][w][0]);
  54.         }
  55.     }
  56.  
  57.     cout << ans << "\n";
  58. } 
  59.  
  60.  
  61. int main(){
  62.  
  63.     int t = 1;
  64.     //cin >> t;
  65.     for(int i = 0; i < t; i++)
  66.         test_case();
  67.  
  68.     return 0;
  69. } 
  70.  
  71.  
  72.  
  73.  
Success #stdin #stdout 0.23s 784840KB
comments (?)
stdin
copy 
4 10
4 5 0
2 3 1
3 3 1
4 2 0
stdout
copy 
9
https://ideone.com/ltzja3
language:
C++14 (gcc 8.3)
created:
2 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!