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
AC × 4
AC × 12
AC × 22
TLE × 2
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