fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long dp[1002][1002][32];
  5. int order[] = {0, 1, 2, 4, 8, 16, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 7, 11, 13,
  6.                     14, 19, 21, 22, 25, 26, 28, 15, 23, 27, 29, 30, 31};
  7.  
  8. void solve() {
  9.     int n, m, kk;
  10.     cin >> n >> m >> kk;
  11.     long long c[kk], p[n], v[n];
  12.     for(int i=0;i<kk;i++) {
  13.         cin >> c[i];
  14.     }
  15.     for(int i=0;i<n;i++) {
  16.         cin >> p[i];
  17.     }
  18.     for(int i=0;i<n;i++) {
  19.         cin >> v[i];
  20.     }
  21.     long long mx = 0;
  22.     memset(dp, 0, sizeof dp);
  23.     for(int k=1;k<32;k++) {
  24.         bool bool_continue = false;
  25.         for(int ii=kk;ii<5;ii++) {
  26.             if(order[k] & (1 << ii)) {
  27.                 bool_continue = true;
  28.             }
  29.         }
  30.         if(bool_continue) continue;
  31.         for(int i=0;i<n;i++) {
  32.             for(int j=0;j<=m;j++) {
  33.                 int x = order[k];
  34.                 for(int y=0;y<kk;y++) {
  35.                     if(i>0)
  36.                         dp[i][j][x] = max(dp[i][j][x], dp[i-1][j][x]);
  37.                     if( (x^(1 << y)) < x) {
  38.                         if(p[i]<=j && c[y]>=v[i]) {
  39.                             // valid sub problem
  40.                             if(i>0) {
  41.                                 dp[i][j][x] = max(dp[i][j][x], dp[i-1][j-p[i]][x^(1 << y)] + v[i]);
  42.                             } else {
  43.                                 dp[i][j][x] = max(dp[i][j][x], v[i]);
  44.                             }
  45.                         }
  46.                     }
  47.                 }
  48.                 if(mx < dp[i][j][x]) {
  49.                     mx = dp[i][j][x];
  50.                 }
  51.             }
  52.         }
  53.     }
  54.     cout << mx << "\n";
  55. }
  56.  
  57. int main() {
  58.     int t;
  59.     cin >> t;
  60.     while(t--) solve();
  61. 	return 0;
  62. }
Runtime error #stdin #stdout 0s 254464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oBGx8B
language:
C++ (gcc 8.3)
created:
7 years 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!