UVa - 562 - Dividing coins

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int dp[103][503], N, Mid;
vector <int> Coin;

int evaluate(int I, int C){
    int gain1, gain2;
    if(I == N)return 0;
    if(dp[I][C] != -1)return dp[I][C];
    if(C+Coin[I] <= Mid)gain1 = Coin[I] + evaluate(I+1, C+Coin[I]);
    else gain1 = 0;
    gain2 = evaluate(I+1, C);
    return dp[I][C] = max(gain1, gain2);
}

int main(){
    int T, C;
    cin >> T;
    while(T--){
        cin >> N;
        int Sum = 0;
        for(int i = 1; i <= N; i++)cin >> C, Sum += C, Coin.push_back(C);
        Mid = Sum / 2;
        memset(dp, -1, sizeof(dp));
        int ans = evaluate(0, 0);
        ans *= 2;
        int real = Sum - ans;
        cout << real << endl;
        Coin.clear();
    }
    return 0;
}