Given n no of students , k -->denoting the minimum total goodness required
There are n boys standing in a line , the ith boy has height Hi and goodness Gi . You are given a number k
Determine the number of ways to select a team of boys such that sum of their goodness is atleast K.
Notes :
-
You can only select a single boy once per team.
-
Two ways of selection are diff if there are atleast 1 boy who is not selected in one
but selected in the other
-
You can move from left to right and select a boy whose height is greater than or equal to the last selected boy
-
You cannot reorder them , but you may skip some of them
N = 3 ,K = 2
H = [1,3,2]
G= [1,2,1]
Answer is 3
Constraints:
1<=T<=10
1<=N<=40
1<=K<=10^9
1<=H[i], G[i]<=10^9
My solution was to use bitmask ( but it works for N<=30 ) -->10^9 only
https://ideone.com/Hy9GcU .
Please suggest me a approach such that it passes for N<=40