All Tracks Algorithms Dynamic Programming Problem

Closing Ceremony at Lolympics
Tag(s):

Algorithms, Dynamic Programming, Medium, Simple-math

Problem
Editorial
Analytics

Lolympics is over! Talented Tanmay and Pretty Parmita have made their country proud by winning $$N$$ medals combined. That's a great achievement, considering it's their first time at the Lolympics. Getting bored during the closing ceremony, they decided to make a game out of the medals they have won.

Both Tanmay and Parmita have a big bag. They gave the $$i^{th}$$ medal a value $$A_i$$. Now they want to count the number of ways in which they can put each medal into either of the bags such that the sum of value of medals in each bag is greater than equal to the magic number $$K$$. Both of them come up with different answers and hence they look forward to you to help them out with the correct answer. Can you live up to their expectations ?

Constraints :

$$1 \le N \le 10^3$$
$$1 \le A_i \le 10^6$$
$$1 \le K \le 10^5$$

Input Format :

The first line contains $$N$$ and $$K$$. The next line contains $$N$$ spaces separated integers, the $$i^{th}$$ integer denotes $$A_i$$.

Output Format :

Output the number of ways in which Tanmay and Parmita can partition the medals in the two bags. Since the value can be huge, output it modulo $$10^9 + 7$$.

SAMPLE INPUT
3 10
5 12 11
SAMPLE OUTPUT
4
Explanation

You can check all $$2^N$$ possibilites:
AAA -> Bad
AAB -> Good
ABA -> Good
ABB -> Bad
BAA -> Bad
BAB -> Good
BBA -> Good
BBB -> Bad

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications