Submission #3823800
Source Code Expand
def func(n, a, x):
# x.sort()
dp = [[[0 for _ in range(sum(x) + 1)] for _ in range(n + 1)] for _ in range(n)]
# table[j][k][s] = x[j+1]までからk枚選んで、その和がsの場合の数
# 0 <= j < N, 0 <= k <= N, s <= sum(x)
# jはインデックスだが,kは選ぶ枚数なので「j < n」「k < n + 1」
# dp[j][k][s] = dp[j-1][k][s] # x[j]を選ばないとき
# + dp[j-1][k-1][s-x[j]] #x[j]を選ぶ場合 (ただし1<=j<=k)
# dp[0][0][0] = 1 #初期値(シード的な)
# dp = 0 # 上記以外の場合
dp[0][0][0] = 1
# j == 0 での処理
dp[0][1][x[0]] = 1
for j in range(1, len(dp)):
for k in range(len(dp[0])):
for s in range(len(dp[0][0])):
# 「j == 0」での事前処理が必要
# if j > 0: # 解説では j > 0 and x[j] >= sらしい
dp[j][k][s] += dp[j-1][k][s]
if k > 0 and s >= x[j]:
dp[j][k][s] += dp[j-1][k-1][s-x[j]]
#print("dp[{}][{}][{}]:{} <- dp[{}][{}][{}]:{} + {}".format(
#j, k, s, dp[j][k][s], j-1, k-1, s-x[j], dp[j-1][k-1][s-x[j]], x[j]))
# if dp[j][k][s] > 0:
# print("dp[{}][{}][{}]:{}---------------".format(j, k, s, dp[j][k][s]))
# else:
# print("dp[{}][{}][{}]:{}".format(j, k, s, dp[j][k][s]))
# for k in range(len(dp[0])):
# for j in range(len(dp)):
# print(dp[j][k])
count = 0
for k in range(1, min(len(dp[0]), len(dp[0][0]) // a + 1)):
# print("dp[{}][{}][{}]:{}".format(n - 1, k, a * k, dp[n - 1][k][a * k]))
count += dp[n-1][k][a*k]
return count
n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
print(func(n, a, x))
"""
print(func(4, 8, [7, 8, 9, 9]))#合計33
print(func(3, 8, [6, 6, 9]))#合計21
print(func(8, 5, [3,6,2,8,7,6,5,9]))#合計46
print(func(33, 3, [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]))#合計46
"""
Submission Info
Submission Time |
|
Task |
C - Tak and Cards |
User |
shunsasa |
Language |
Python (3.4.3) |
Score |
200 |
Code Size |
2156 Byte |
Status |
TLE |
Exec Time |
2108 ms |
Memory |
55412 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
0 / 100 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
example_01.txt, example_02.txt, example_03.txt, example_04.txt |
Subtask1 |
example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt |
All |
example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt |
Case Name |
Status |
Exec Time |
Memory |
example_01.txt |
AC |
18 ms |
3064 KB |
example_02.txt |
AC |
18 ms |
3064 KB |
example_03.txt |
AC |
19 ms |
3064 KB |
example_04.txt |
AC |
74 ms |
3956 KB |
subtask1_01.txt |
AC |
105 ms |
4724 KB |
subtask1_02.txt |
AC |
123 ms |
4852 KB |
subtask1_03.txt |
AC |
123 ms |
4852 KB |
subtask1_04.txt |
AC |
20 ms |
3064 KB |
subtask1_05.txt |
AC |
71 ms |
4084 KB |
subtask1_06.txt |
AC |
18 ms |
3064 KB |
subtask1_07.txt |
AC |
18 ms |
3064 KB |
subtask1_08.txt |
AC |
80 ms |
4212 KB |
subtask1_09.txt |
AC |
61 ms |
3828 KB |
subtask2_01.txt |
AC |
1748 ms |
40612 KB |
subtask2_02.txt |
AC |
1729 ms |
40732 KB |
subtask2_03.txt |
AC |
1596 ms |
35124 KB |
subtask2_04.txt |
TLE |
2108 ms |
55412 KB |
subtask2_05.txt |
TLE |
2108 ms |
55412 KB |
subtask2_06.txt |
AC |
89 ms |
4340 KB |
subtask2_07.txt |
AC |
1735 ms |
33780 KB |
subtask2_08.txt |
AC |
443 ms |
11368 KB |
subtask2_09.txt |
AC |
549 ms |
13544 KB |
subtask2_10.txt |
AC |
1083 ms |
24136 KB |
subtask2_11.txt |
AC |
1084 ms |
25404 KB |