Advertisement
madhukeshk3

Two largest pipe of maximum length - Samsung R&D

Sep 7th, 2020
127
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve()
  5. {
  6.     int n;
  7.     cin>>n;
  8.  
  9.     int arr[n+1];
  10.  
  11.     for(int i=1;i<=n;i++)
  12.         cin>>arr[i];
  13.  
  14.     int dp[1005][1005];
  15.     int dp1[1005][1005];
  16.  
  17.     for(int i=0;i<=1000;i++)
  18.     {
  19.         for(int j=0;j<=1000;j++)
  20.             dp[i][j]=0;
  21.     }
  22.  
  23.     dp[0][0]=1;
  24.  
  25.     for(int i=1;i<=n;i++)
  26.     {
  27.         for(int j=0;j<=1000;j++)
  28.         {
  29.             for(int k=0;k<=1000;k++)
  30.             {
  31.                 if(j>=arr[i]){
  32.                     if(dp[j-arr[i]][k])
  33.                     {
  34.                         dp1[j][k]=1;
  35.                     }
  36.                 }
  37.                 if(k>=arr[i]){
  38.                     if(dp[j][k-arr[i]])
  39.                     {
  40.                         dp1[j][k]=1;
  41.                     }
  42.                 }
  43.                 if(dp[j][k]){
  44.                     dp1[j][k]=1;
  45.                 }
  46.             }
  47.         }
  48.  
  49.         for(int j=0;j<=1000;j++)
  50.         {
  51.             for(int k=0;k<=1000;k++)
  52.             {
  53.                 dp[j][k]=dp1[j][k];
  54.                 dp1[j][k]=0;
  55.             }
  56.         }
  57.     }
  58.  
  59.     int ans=0;
  60.  
  61.     for(int i=1;i<=1000;i++)
  62.     {
  63.         if(dp[i][i])
  64.         {
  65.             ans=i;
  66.         }
  67.     }
  68.    
  69.     cout<<ans<<endl;
  70.  
  71.     return;
  72. }
  73.  
  74. int main()
  75. {
  76.     int t;
  77.     cin>>t;
  78.  
  79.     while(t--)
  80.         solve();
  81.  
  82.     return 0;
  83. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement