結果

問題 No.189 SUPER HAPPY DAY
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-11-17 13:22:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,657 ms / 5,000 ms
コード長 848 bytes
コンパイル時間 388 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 87,888 KB
最終ジャッジ日時 2024-11-17 13:23:24
合計ジャッジ時間 53,765 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,773 ms
81,992 KB
testcase_01 AC 1,779 ms
83,164 KB
testcase_02 AC 1,755 ms
81,760 KB
testcase_03 AC 1,809 ms
84,448 KB
testcase_04 AC 1,802 ms
83,932 KB
testcase_05 AC 1,806 ms
83,592 KB
testcase_06 AC 1,791 ms
84,324 KB
testcase_07 AC 1,825 ms
84,308 KB
testcase_08 AC 1,809 ms
83,904 KB
testcase_09 AC 1,810 ms
84,068 KB
testcase_10 AC 1,785 ms
84,448 KB
testcase_11 AC 1,786 ms
83,848 KB
testcase_12 AC 1,747 ms
84,448 KB
testcase_13 AC 2,242 ms
85,836 KB
testcase_14 AC 2,541 ms
87,772 KB
testcase_15 AC 2,102 ms
85,964 KB
testcase_16 AC 2,079 ms
85,476 KB
testcase_17 AC 2,152 ms
85,324 KB
testcase_18 AC 2,085 ms
85,224 KB
testcase_19 AC 2,657 ms
87,888 KB
testcase_20 AC 1,700 ms
84,956 KB
testcase_21 AC 1,868 ms
85,728 KB
testcase_22 AC 1,629 ms
85,352 KB
testcase_23 AC 1,910 ms
82,824 KB
testcase_24 AC 1,831 ms
82,756 KB
testcase_25 AC 2,519 ms
82,916 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

s,t=input().split()
M=10**9+9
L=202
s=s.zfill(L)
t=t.zfill(L)
q=[[[0]*(L*20+1) for j in range(2)] for i in range(2)]
q[0][0][0]=1
for p in range(L):
  c1=int(s[p])
  c2=int(t[p])
  nq=[[[0]*(L*20+1) for j in range(2)] for i in range(2)]
  for d in range(-L*10,L*10+1):
    for q1 in range(10):
      for q2 in range(10):
        if q[0][0][d]!=0:
          if q1<=c1 and q2<=c2:
            nq[q1<c1][q2<c2][d+q1-q2]+=q[0][0][d]
        if q[0][1][d]!=0:
          if q1<=c1:
            nq[q1<c1][1][d+q1-q2]+=q[0][1][d]
        if q[1][0][d]!=0:
          if q2<=c2:
            nq[1][q2<c2][d+q1-q2]+=q[1][0][d]
        if q[1][1][d]!=0:
          nq[1][1][d+q1-q2]+=q[1][1][d]
  q=nq
  for d in range(-L*10,L*10+1):
    q[0][0][d]%=M
    q[0][1][d]%=M
    q[1][0][d]%=M
    q[1][1][d]%=M
print((q[0][0][0]+q[0][1][0]+q[1][0][0]+q[1][1][0]-1)%M)
0