Light OJ-1147/ UVA 10032 - TUG OF WAR (DP, Bitmasks )

Light OJ-1147/ UVA 10032 - TUG OF WAR (DP, Bitmasks )

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     200005
#define inf    2000000010
#define eps    1e-9
///===============================///

int ar[105];
ll dp[MX+2];
int main() {
    int tc, cs = 1, n;
    S(tc);
    while(tc--) {
        S(n);
        ll sm = 0LL;
        for(int i=1; i<=n; i++) {
            S(ar[i]);
            sm += ar[i];
        }
        int hf = ((sm+1) / 2);
        ll od = (n + 1) / 2;
        ll ev = (n / 2);

        CLR(dp);
        /// dp[ j ]= Bitmasks of valid ways to make sum j; if  K'th bit is on it represent K nos of weights needed to make sum j.
        /// Total on bits on dp[ j ]=Total no of ways to make sum j.[ __builtin_popcount(dp[j]) ]
        dp[0] = 1LL;
        for(int i = 1; i <= n; i++) {
            for(int j = hf; j >= ar[i]; j--) { /// Coin can be taken only once;
                dp[j] = ( dp[j] | ( dp[ j - ar[i] ]<<1LL ));

            }
        }
        printf("Case %d: ",cs++);
        for(ll i = hf; i >= 0; i--) {
            if( (dp[i] & (1LL << od)) || (dp[i] & (1LL << ev)) ) {
                printf("%lld %lld\n", min(i, sm - i), max(i, sm - i) );
                break;
            }
        }
    }
    return 0;
}