Find Your Solution Here

UVA

UVA 562 – Dividing coins solution

Problem Link–https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=503

Solution:

#include<bits/stdc++.h>

using namespace std;
int dp[105][6000];
int isSubarray(int a[],int n,int sum,int x){
    if(sum<=0){
        return x;
    }
    if(n==0){
        if(sum-a[n]>=0){
            x+=a[n];
        }
        return x;
    }
    if(a[n]>sum){
        return dp[n][x]=isSubarray(a,n-1,sum,x);
    }

    if(dp[n][x]==-1){
        return dp[n][x]=max(isSubarray(a,n-1,sum,x), isSubarray(a,n-1,sum-a[n],x+a[n]));
    }
    else{
        return dp[n][x];
    }

}
int main()
{
    int n,m;
    cin>>n;
    while(n--)
    {
        cin>>m;
        int a[m+10],sum=0;
        for(int i=0;i<m;i++){
            cin>>a[i];
            sum+=a[i];
        }
        memset(dp,-1,sizeof(dp));
        cout<<sum-2*isSubarray(a,m-1,sum/2,0)<<endl;
    }

}

Leave a Reply