UVa 711 Dividing Up

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

ll tot,coins[8],n,mem[8][20008*6];

// have to divide two grps of coin equally
// make half of total from given coins n values

ll call(ll i, ll feas)
{
    if(feas==0) return 1;
    if(feas<0 or i==7) return 0;

    if(mem[i][feas]!=-1) return mem[i][feas];

    mem[i][feas] = 0;

    for(int j=0; j<=coins[i]; j++)
    {
        mem[i][feas] |= call(i+1, feas-i*j);
        if(mem[i][feas]==1) break;
    }
    return mem[i][feas];
}

int main()
{
    ll cs = 0;
    while(1)
    {
        tot = 0;
        FOR(i,1,6) scl(coins[i]), tot += i*coins[i];

        if(tot==0) break;

        printf("Collection #%lld:\n", ++cs);

        memset(mem,-1,sizeof mem);

        ll rs;

        if(tot%2) rs = 0;
        else rs = call(1,tot/2);

        if(rs==0) printf("Can't be divided.\n");
        else printf("Can be divided.\n");

        puts("");
    }
    return 0;
}