API tools faq
paste
S_Aditya

Untitled

S_Aditya
Mar 24th, 2021 (edited)
72
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 2004; //taken according to constraints
  5.  
  6. int main()                  
  7. {
  8.     int n; cin >> n;
  9.  
  10.     int a[n];
  11.  
  12.     for(int i = 0; i < n; i++)
  13.     cin >> a[i];
  14.  
  15.     int dp[N][N]; memset(dp, 0, sizeof(dp));
  16.  
  17.     dp[0][0] = 1; //base case, no considerations, no elements in bags  
  18.  
  19.     for(int i = 0; i < n; i++)
  20.     {
  21.         for(int bag1 = N - 1; bag1 >= 0; bag1--)
  22.         {
  23.             for(int bag2 = N - 1; bag2 >= 0; bag2--)
  24.             {
  25.                 //put rod in bag1
  26.                 if(bag1 + a[i] < N)
  27.                 dp[bag1 + a[i]][bag2] |= dp[bag1][bag2];
  28.  
  29.  
  30.                 //put rod in bag2
  31.                 if(bag2 + a[i] < N)
  32.                 dp[bag1][bag2 + a[i]] |= dp[bag1][bag2];
  33.             }
  34.         }
  35.     }
  36.  
  37.     int ans = 0;
  38.  
  39.     for(int i = 0; i < N; i++)
  40.     if(dp[i][i])
  41.     ans = max(ans, i);
  42.  
  43.     cout << ans;
  44.  
  45.     return 0;
  46. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!