結果

問題 No.189 SUPER HAPPY DAY
コンテスト
ユーザー roaris
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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