HackerRank The Indian Job problem solution

In this HackerRank The Indian Job problem solution 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 guards will return after G minutes, they have to finish their tasks within G minutes. The robbers want to know if there exists an arrangement such that the demands of each robber are satisfied and also they are not caught?

Problem solution in Python.

T = int(input())
for t in range(T):
   N, G = map(int, input().split())
   A = [int(x) for x in input().split()]
   s = set([0])
   for x in A:
      for t in list(s):
         s.add(x + t)
   x = sum(A)
   for t in s:
      if t <= G and x - t <= G:
         print('YES')
         break
   else:
      print('NO')

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the indianJob function below.
     */
    static String indianJob(int g, int[] arr) {
        /*
         * Write your code here.
         */
        int n = arr.length;
        int[][] dp = new int[n+1][g+1];
        
    int sum = 0;
    for (int i=0; i<n; i++ )
    {
        sum += arr[i];
    }
 
   
    for (int i=1; i<=n; i++)
        for (int j=1; j<=g; j++)
            if (arr[i-1] <= j)
                dp[i][j] = Math.max(dp[i-1][j],
                        arr[i-1] + dp[i-1][j-arr[i-1]]);
            else
                dp[i][j] = dp[i-1][j];
 
    if(sum-dp[n][g] <= g) {
        return "YES";
    } else {
        return "NO";
    }

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            String[] ng = scanner.nextLine().split(" ");

            int n = Integer.parseInt(ng[0].trim());

            int g = Integer.parseInt(ng[1].trim());

            int[] arr = new int[n];

            String[] arrItems = scanner.nextLine().split(" ");

            for (int arrItr = 0; arrItr < n; arrItr++) {
                int arrItem = Integer.parseInt(arrItems[arrItr].trim());
                arr[arrItr] = arrItem;
            }

            String result = indianJob(g, arr);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<bitset>
#include<iomanip>
#include<iostream>
#include<cmath>
using namespace std;

#define rep(i,x,y) for(i=x;i<=y;i++)
#define _rep(i,x,y) for(i=x;i>=y;i--)
#define CL(S,x) memset(S,x,sizeof(S))
#define CP(S1,S2) memcpy(S1,S2,sizeof(S2))
#define ALL(x,S) for(x=S.begin();x!=S.end();x++)
#define sqr(x) ((x)*(x))
#define mp make_pair
#define fi first
#define se second
#define upmin(x,y) x=min(x,y)
#define upmax(x,y) x=max(x,y)
#define pb push_back
#define COUT(S,x) cout<<fixed<<setprecision(x)<<S<<endl

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

template<class T> inline void read(T&x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x=-x;};
inline char getc(){char c;for(c=getchar();c<=32;c=getchar());return c;}

const int N=110;
int T,n,i,j,k,l,p,s,x;
bitset<11111> S;

int main()
{
   
	for(read(T);T;T--)
	{
		read(n);read(l);s=0;
		S=0;S[0]=1;
		rep(p,1,n)
		{
			read(x);
			s+=x;
			S|=S<<x;
		}
		int ans=s;
		rep(i,0,s)
		if(S[i])upmin(ans,max(i,s-i));
		if(ans<=l)printf("YESn");else printf("NOn");
	}
	
    scanf("n");
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
	int T,G,N,A[101];
	scanf("%d",&T);
	for(int t=0;t<T;t++) {
		scanf("%d %d",&N,&G);
		int total=0;
		int possible = 1;
		for(int n=1;n<N+1;n++) {
			scanf("%d",A+n);
			total += A[n];
			if(A[n]>G) possible = 0;
		}
		if(total>2*G)possible = 0;
		if(possible && N>2){
			int T[10001];//array of possible times
			for(int i=0;i<100*N+1;i++) T[i] = 0;
			T[A[1]] = 1;
			int itmax = A[1];
			for(int n=2;n<=N;n++) {
				if(itmax+A[n]<=G) {
					itmax += A[n];
					T[itmax] = 1;
				}
				for(int in=itmax-1;in>=0;in--) {
					if(T[in]) {
						if(in+A[n]<=G) {
							T[in+A[n]]=1;
							if(in+A[n]>itmax) itmax = in+A[n];
						}
					}
				}
				T[A[n]] = 1;
			}
			if(total-itmax>G) possible = 0;
		}
		if(possible){
			printf("YESn");
		} else {
			printf("NOn");
		}
		
	}
	return 0;
}