The Indian Job

It is the Indian version of the famous heist “The Italian Job”. N robbers have already broken into the National Museum and are just about to get inside the main vault which is full of jewels. They were lucky that just as they broke into the museum, the guard was leaving the museum for exactly G minutes. But there are other problems too. The main vault has heat sensors that if at any moment of time there are more than two people present in the vault, the alarm goes off.

To collect the jewels, the ith robber needs to be inside the vault for exactly A[i]minutes, 0 <= i < N, in one continuous stretch. As guard will return after G minutes, they have to finish their tasks within G minutes. The robbers want to know if there exists any arrangement such that demands of each robber is satisfied and also they are not caught?

Gotchas
If a robber goes inside the vault at a time “X” and at the same time another robber comes out, it’s equivalent to saying they were never in the vault at the same time.
Similarly, when the guard gets inside vault at time G and a robber comes out exactly at time G, the guard will not be able see the robber.

Input Format
The first line contains an integer T denoting the number of testcases. T testcases follow. Each testcase consists of two lines. First line contains two space separated integers denoting N and G denoting the number of thieves and duration for which guard leaves the museum.
The next line contains N space separated numbers where the ith integer, A[i] represents the time the ith robber needs to be in the vault.

Output Format
For each testcase print YES if there exists such an arrangement or NO otherwise in a newline.

Constraints
1 <= T <= 20
1 <= N <= 100
0 <= G <= 1000000 (106)
0 <= A[i] <= 100

Sample Input

2
3 4
2 4 2
3 2
2 4 2

Sample Output

YES
NO

Explanation
Test case #00: In first testcase, one possible arrangement is:
at t=0, robber1 goes inside and comes out at t=2
at t=0, robber2 goes inside and comes out at t=4
at t=2, robber3 goes inside and comes out at t=4

Test case #01: No possible arrangement is possible in second testcase.

solution--> it a partition problem . we need to max value of sub array minimum then G(guard time).

References:
http://en.wikipedia.org/wiki/Partition_problem

code-->

#include<iostream>

using namespace std ;

void calculate(int arr[], int g , int n)

{

    int sum = 0 , max;

    int i, j;

   

    // Caculcate sun of all elements

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

      sum += arr[i];

     

   

    bool part[g+1][n+1];

  

    // initialize top row as true

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

      part[0][i] = true;

       

    // initialize leftmost column, except part[0][0], as 0

    for (i = 1; i <= g; i++)

      part[i][0] = false;     

      

     // Fill the partition table in botton up manner 

     for (i = 1; i <= g; i++)  

     {

       for (j = 1; j <= n; j++)  

       {

         part[i][j] = part[i][j-1];

         if (i >= arr[j-1])

           part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];

       }        

     }

    

    for(i=g;i>=0;i--){

        

        if(part[i][n]==true){

            max=i ;

            break ;

        }

    }    

    if(2*max>=sum)

        cout << "YES" << endl ;

    else

        cout << "NO"  << endl ;   

}   

  

int main(){

  int t ;

   cin >> t ;

  while(t--){

    int  n , g , i;

    cin >> n ;

    cin >> g ;

     int arr[n];

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

      cin >> arr[i];

    calculate(arr,g,n);

  } 

}