SHARE
TWEET

Banner_Samsung

lelouche29 Sep 18th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #define temp 1000
  3. using namespace std;
  4.  
  5. int n, a[50];
  6. int dp[51][2002];
  7. bool visited[51][2002];
  8.  
  9. int solve(int index, int sum){
  10.     if( visited[index][sum + temp])
  11.         return dp[index][sum + temp];
  12.    
  13.     visited[index][sum+temp] = true;
  14.    
  15.     int &ans=dp[index][sum+temp];
  16.     ans=-temp;
  17.  
  18.     if(index == n) {
  19.         if(sum == 0) ans=0;
  20.     }
  21.    
  22.     else{
  23.         int x = max( ans, a[index] + solve(index + 1, sum + a[index]));
  24.         int y = max(ans, 0         + solve(index + 1, sum - a[index]));
  25.         int z = max(ans, 0         + solve(index + 1, sum));
  26.         ans = max(x, max(y, z));
  27.     }
  28.     return ans;
  29. }
  30.  
  31. int main(){
  32.    
  33.     cin>>n;
  34.     for(int i = 0; i<n; i++)cin>>a[i];
  35.    
  36.     if(solve(0,0) <= 0)
  37.       cout<<0<<endl;
  38.     else
  39.       cout<<solve(0,0)<<endl;
  40.    
  41.     return 0;
  42. }
RAW Paste Data
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
 
Top