結果

問題 No.189 SUPER HAPPY DAY
ユーザー roarisroaris
提出日時 2019-10-30 19:22:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 833 ms / 5,000 ms
コード長 749 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 139,504 KB
最終ジャッジ日時 2024-09-14 21:55:44
合計ジャッジ時間 8,295 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
68,308 KB
testcase_01 AC 80 ms
76,528 KB
testcase_02 AC 57 ms
68,280 KB
testcase_03 AC 76 ms
76,016 KB
testcase_04 AC 75 ms
76,400 KB
testcase_05 AC 79 ms
76,364 KB
testcase_06 AC 80 ms
76,392 KB
testcase_07 AC 79 ms
76,608 KB
testcase_08 AC 75 ms
76,088 KB
testcase_09 AC 80 ms
76,028 KB
testcase_10 AC 77 ms
76,456 KB
testcase_11 AC 78 ms
76,004 KB
testcase_12 AC 75 ms
76,568 KB
testcase_13 AC 422 ms
96,196 KB
testcase_14 AC 520 ms
102,916 KB
testcase_15 AC 481 ms
102,148 KB
testcase_16 AC 518 ms
107,096 KB
testcase_17 AC 568 ms
109,140 KB
testcase_18 AC 495 ms
100,936 KB
testcase_19 AC 680 ms
112,096 KB
testcase_20 AC 308 ms
86,464 KB
testcase_21 AC 341 ms
87,092 KB
testcase_22 AC 119 ms
77,632 KB
testcase_23 AC 458 ms
107,316 KB
testcase_24 AC 474 ms
107,516 KB
testcase_25 AC 833 ms
139,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

def calc(M):
    L = len(M)
    dp = [[[0] * 2001 for _ in range(2)] for _ in range(L+1)]
    dp[0][0][0] = 1
    
    for i in range(L):
        for j in range(2):
            for k in range(2001):
                for d in range(10 if j else int(M[i])+1):
                    if k+d <= 2000:
                        dp[i+1][j|(d<int(M[i]))][k+d] += dp[i][j][k]
    
    dic = defaultdict(int)
    
    for i in range(2):
        for j in range(2001):
            if dp[L][i][j] > 0:
                dic[j] += dp[L][i][j]
    
    dic[0] = 0
    
    return dic

M, D = input().split()
MOD = 10**9+9
dic1, dic2 = calc(M), calc(D)
ans = 0

for k, v in dic1.items():
    ans += v*dic2[k]
    ans %= MOD

print(ans)
0