## Polynomial Time Boolean Satisfiability

View as PDF

Points: 15 (partial)
Time limit: 7.0s
Memory limit: 512M

Authors:
Problem types

The boolean satisfiability problem is a famous problem in computer science. You are given $$2^N$$ booleans, and a list of $$N$$ numbers. A boolean is satisfied if a subset from the $$N$$ numbers sum up to less than or equal to $$K$$. What is the maximum number of booleans that can be satisfied?

Note: the empty subset sums up to 0.

#### Input Specification

On the first line, there are two integers $$N$$, and $$K$$, separated by a space.

On the second line is a space separated list of the $$N$$ integers.

Each line is followed by one line feed character (ASCII code 0x0a).

There are no trailing spaces or empty lines.

#### Output Specification

One integer, the number of subsets that sum to less than or equal to $$K$$.

#### Constraints

$${-2^{31} \le n_i \lt 2^{31}}$$

$${-2^{31} \le K \lt 2^{31}}$$

For all subset sums $$k_i$$,

$${-2^{31} \le k_i \lt 2^{31}}$$

$${1 \le N \le 49}$$

For 2 of the 15 available marks, $$N \le 20$$

#### Sample Input 1

10 10
8 2 10 10 6 1 10 10 1 5

#### Sample Output 1

33

#### Sample Input 2

5 5
1 2 3 4 5

#### Sample Output 2

10