Aloo Kachori

• Problem Description

  
  kenny has received a package of N ingredients from Aloo uncle and Kachori aunty as their Christmas gift. kenny decides to make dishes with every possible combination of these N ingredients. (Note: A dish with 0 ingredients is also possible. kenny uses it as an excuse for serving air to their airy customers). Every ingredient from the package has a taste score between 1 and 10.
  
  Now kenny has customers on two planets, planet A and planet B. People from planet A like all the ingredients very much. And hence for every dish given to them, planet A will pay kenny an amount, which, in Alterian dollars, equals the sum of the taste scores of all the ingredients present in the dish minus the sum of the taste scores of all the ingredients not present in the dish.
  
  People from planet B dont like the ingredients at all. So for every dish given to planet B, planet B will pay kenny Alterian dollars equal to the sum of the taste scores of all the ingredients not present in the dish minus the sum of the taste scores of all the ingredients present in the dish.
  
  kenny can only make a single dish from a particular combination of ingredients. And they can send a dish either to planet A or planet B, but not both. You have to find out the maximum amount of money kenny will make by distributing all the dishes made with these ingredients on planet A and planet B.
  
  Report the maximum amount modulo 107.
  Input
  
  The first line contains T, the number of test cases.
  
  Each test case begins with N, the number of ingredients
  
  The next line for the test case contains N space-separated integers, which are the taste scores of the ingredients.
  Output
  
  For each test case, output the value as asked in a separate line.
  Constraints
  
  1 <= T <= 100
  1 <= N <= 1000
  1 <= Taste scores of ingredients <= 10
  1 <= Sum of N over all Test Cases <= 1000
  

• Test Case 1

  
  Input (stdin)

  1
  
  3
  
  1 2 3
  
  

  Expected Output

  24

• Test Case 2

  
  Input (stdin)

  2
  
  2
  
  1 3
  
  3
  
  1 4 5
  
  

  Expected Output

  12
  
  40

Solution

#include <stdio.h>

#include <stdlib.h>

#define MOD 10000000

int main()

{

  int T,N,sum,values[1000],i,j;

  long long dp[10001],total;

  scanf("%d",&T);

  while(T--)

  {

    scanf("%d",&N);

    sum=0;

    for(i=0;i<N;i++)

    {

      scanf("%d",&values[i]);

      sum=sum+values[i];

    }

    for(i=0;i<=sum;i++)

    {

      dp[i]=0;

      dp[0]=1;

    }

    for(i=0;i<N;i++)

    {

      for(j=sum;j>=0;j--)

      {

        if(dp[j]>0)

        {

          dp[j+values[i]]=((dp[j+values[i]])+(dp[j]))%MOD;

        }

      }

    }

    total=0;

    for(i=0;i<=sum;i++)

    {

      if(dp[i]>0)

      {

        long long inc=((long long)((((long long)abs(sum-2*i)))*(dp[i])))%MOD;

        total=(total+inc)%MOD;

      }

    }

      printf("%Ld\n",total);

  }

  return 0;

}