Problem:


Problem D: 僕の友達は小さい

僕には、たくさんの友達がいる。どの友達も、とても小さい。

僕は、よく友達と一緒に出かける。何人かの友達をリュックに入れて、一緒に出かける。

僕は毎朝、その日一緒に出かける友達を決める。空のリュックに、１人ずつ友達を入れていく。

僕は、あまり力が強くない。だから、同時に運べる友達の重さには限界がある。

僕は、重さの限界を超えないように友達を入れていく。どの順番で入れていくかは気分次第。

僕は、入れられる友達がまだ残っている限り、入れるのを止めない。決して止めない。

……ところで、リュックに入った友達の組み合わせは、全部で何パターンあるんだろう？

Input

N W

w1

w2

.

.

.

wn

入力の１行目には、整数N（1 ≤ N ≤ 200）と整数W（1 ≤ W ≤ 10,000）が、この順に空白区切りで書かれている。整数N は友達の数を、整数W は同時に運べる重さの限界をあらわす。重さの合計がW より大きいと運ぶことはできない。

続くN 行には、友達の重さをあらわす整数が書かれている。整数wi（1 ≤ wi ≤ 10,000）が、i 番目の友達の重さをあらわす。

Output

最終的にリュックに入っている友達の組み合わせは何通り考えられるか。その総数を1,000,000,007
で割った余りを出力せよ。なお1,000,000,007 は素数である。

「誰もリュックに入っていない」も１通りとして数えることに注意せよ。

Sample Input 1

4 8
1
2
7
9

Sample Output 1

2

Sample Input 2

4 25
20
15
20
15

Sample Output 2

4

Sample Input 3

6 37
5
9
13
18
26
33

Sample Output 3

6



Sample input:
4 8
1
2
7
9


Sample output:
2

Submission status: Wrong Answer

Solution code:
N, W = map(int, raw_input().split())
L = sorted([int(raw_input()) for _ in xrange(N)])
total = sum(L)
dp = [1] + [0] * W
ans = 0 if total > W else 1
for i, w in zip(xrange(N, -1, -1), L[::-1]):
    total -= w
    res = W - total
    if res >= 0:
        ans += sum(dp[max(0, res - w + 1):res + 1])
    for j in xrange(W, w - 1, -1):
        dp[j] += dp[j - w]
print ans

Submission status: Wrong Answer

Solution code:
N, W = map(int, raw_input().split())
L = sorted([int(raw_input()) for _ in xrange(N)])
total = sum(L)
dp = [1] + [0] * W
ans = 0 if total > W else 1
for i, w in zip(xrange(N, -1, -1), L[::-1]):
    total -= w
    res = W - total
    if res >= 0:
        ans = (ans + sum(dp[max(0, res - w + 1):res + 1])) % (10**9 + 1)
    for j in xrange(W, w - 1, -1):
        dp[j] += dp[j - w]
print ans

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
L = sorted([int(raw_input()) for _ in xrange(N)])
total = sum(L)
dp = [1] + [0] * W
ans = 0 if total > W else 1
for i, w in zip(xrange(N, -1, -1), L[::-1]):
    total -= w
    res = W - total
    if res >= 0:
        ans = (ans + sum(dp[max(0, res - w + 1):res + 1])) % (10**9 + 7)
    for j in xrange(W, w - 1, -1):
        dp[j] += dp[j - w]
print ans

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
MOD = 10**9 + 7
ws = [int(input()) for i in range(N)]
ws.sort(reverse=1)
su = sum(ws)
dp = [0]*(W+1)
dp[0] = 1
ans = 0
if su <= W:
    ans += 1
for i in range(N):
    w = ws[i]
    su -= w
    ans += sum(dp[max(W+1-w-su, 0):max(W+1-su, 0)]) % MOD
    for j in range(W, w-1, -1):
        dp[j] += dp[j-w]
        dp[j] %= MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = []
for i in range(N):
    w.append(int(input()))
w.sort()
summ = 0
ans = 0
for num, wi in enumerate(w):
    if num == N - 1:
        if sum(w) - w[-1] <= W and W - sum(w) - w[-1] < w[-1]:
            ans += 1
        break
    dp = [[0] * (W + 1) for i in range(N - num)]
    dp[0][0] = 1
    for n in range(N - num - 1):
        dpn1 = dp[n + 1]
        dpn = dp[n]
        for k in range(W + 1):
            if k - w[num + n + 1] >= 0:
                dpn1[k] = dpn[k] + dpn[k - w[num + n + 1]]
            else:
                dpn1[k] = dpn[k]
    for i in range(max(W - summ - wi + 1,0), W - summ + 1):
        ans += dp[-1][i]
        ans %= 10 ** 9 + 7
    summ += wi
    if W < summ:
        break
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n,w):
        a = sorted([I() for _ in range(n)], reverse=True)
        dp = [0] * (w+1)
        dp[0] = 1
        sm = sum(a)
        if sm <= w:
            return 1
        r = 0
        for c in a:
            sm -= c
            if w >= sm:
                r += sum(dp[max(0,w-sm-c+1):w-sm+1])
                r %= mod
            for j in range(w-c,-1,-1):
                dp[j+c] += dp[j]
                dp[j+c] %= mod
        return r % mod

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        break

    return '\n'.join(map(str,rr))


print(main())