fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dp[1001][1001];
  4. int fun(int arr[],int wt[],int n,int i,int j)
  5. {
  6.     if(i==n)
  7.     {
  8.         if(j<0)
  9.             return -1000005;
  10.         return 0;
  11.     }
  12.     if(j<0)
  13.         return -1000005;
  14.     if(j==0)
  15.         return 0;
  16.     if(dp[i][j]!=-1)
  17.         return dp[i][j];
  18.     return dp[i][j]=max(fun(arr,wt,n,i+1,j-wt[i])+arr[i],fun(arr,wt,n,i+1,j));
  19. }
  20. int main() {
  21.     int t;
  22.     cin>>t;
  23.     while(t--)
  24.     {
  25.         memset(dp,-1,sizeof(dp));
  26.         int n,w;
  27.         cin>>n;
  28.         cin>>w;
  29.         int arr[n];
  30.         int wt[n];
  31.         for(int i=0;i<n;i++)
  32.             cin>>arr[i];
  33.         for(int i=0;i<n;i++)
  34.             cin>>wt[i];
  35.         int ans=fun(arr,wt,n,0,w/2);
  36.         cout<<ans<<endl;
  37.     }
  38. 	return 0;
  39. }
Success #stdin #stdout 0.01s 7592KB
comments (?)
stdin
copy 
1
4
15
2 4 4 5
2 2 3 4
stdout
copy 
10
https://ideone.com/Q74l6x
language:
C++14 (gcc 8.3)
created:
3 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!