Bittu is a chocolate-loving kid playing a game where he can choose bags of chocolates. Each bag has a different number of chocolates. Bittu starts with k chocolates and 1 point. He has two choices for each bag:
- Accept the Bag:
• If the chocolates in the bag are fewer than or equal to the chocolates Bittu has, he won't accept the bag. Instead, he'll deduct the bag's chocolates from his stash and gain one point.
• If the chocolates in the bag are more than what Bittu has, he can accept the bag. His chocolate stash increases by the bag's chocolates, and he loses one point.
- Ignore the Bag:
• Bittu can choose to ignore any number of bags without any consequences.
The goal is to maximize Bittu's points. Given an array "chocolates" with the number of chocolates in each bag, and the initial number of chocolates Bittu has, determine the maximum points he can achieve by selecting bags wisely
In simpler terms, he wants to acquire the maximum number of points while following the above mentioned rules.
Constraints
n — length of the array
1 <= n <= 1000
0 <= chocolates[i] <= 10^5
Input
First line consisting of the number of chocolates in n bags separated by space.
Second line consists of an integer depicting the number of chocolates that Bittu has, initially.
Output
Print the maximum points that Bittu can acquire.
Someone please help me with this problem. I am trying a DP solution but it is giving MLE.
Comments (0)
