Advertisement
ismaeil

Algo 1Q

Aug 12th, 2020
360
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int,int> ii;
  5. #define OO INT_MAX
  6. #define S second
  7. #define F first
  8.  
  9. const int  N = 1e2 + 2e1;
  10. int n ,Sum ,A[N];
  11. ii Dp[N][N * 2];
  12.  
  13. ii Calc(int i ,int sumA){
  14.     int sumB = Sum - sumA;
  15.  
  16.     if( i == n + 1 ){
  17.         if( abs(sumA - sumB ) < abs(Dp[n][sumA].F - Dp[n][sumA].S) ){
  18.             Dp[n][sumA].F  = sumA;
  19.             Dp[n][sumA].S = sumB;
  20.         }
  21.         return Dp[n][sumA];
  22.     }
  23.  
  24.     ii &Re = Dp[i][sumA];
  25.     if( Re.S != OO ) return Re;
  26.  
  27.     ii c1 = Calc(i+1 ,sumA);
  28.     ii c2 = Calc(i+1 , sumA + A[i]);
  29.  
  30.     if( abs(c1.F - c1.S) < abs(c2.F - c2.S) )
  31.          Re = c1;
  32.     else Re = c2;
  33.  
  34.     return Re;
  35. }
  36.  
  37. int main() {
  38.     cin >> n;
  39.     for(int i=1 ; i <= n ; i++)
  40.         cin >> A[i] ,Sum += A[i];
  41.  
  42.     // memset Dp (OO ,0)
  43.     for(int i = 0 ; i < N ; i++){
  44.         for(int j = 0 ; j < N * 2 ; j ++){
  45.             Dp[i][j].F  = 0;
  46.             Dp[i][j].S = OO;
  47.         }
  48.     }
  49.  
  50.     ii Ans = Calc( 1 , 0 );
  51.     cout << Ans.F << ' ' << Ans.S << endl;
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement