UVa 562 Dividing Coins

562.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define PB push_back
#define endl '\n'

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int INF = ~(1<<31);

int n, total;
int dp[107][50005], A[107];

int f(int i, int sum) {
    if(i == n) return abs(sum - (total - sum));
    if(~dp[i][sum]) return dp[i][sum];

    int &val = dp[i][sum];
    val = min( f( i + 1, sum ), f( i + 1, sum + A[i] ) );
    return val;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--) {
        memset(dp, -1, sizeof dp);

        cin >> n;
        for(int i=0; i<n; i++) cin >> A[i];
        total = accumulate(A, A + n, 0);
        cout << f(0, 0) << endl;
    }

    return 0;
}