結果
問題 | No.533 Mysterious Stairs |
ユーザー |
![]() |
提出日時 | 2019-07-09 15:20:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 95 ms / 5,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 489 ms |
コンパイル使用メモリ | 82,416 KB |
実行使用メモリ | 91,524 KB |
最終ジャッジ日時 | 2024-10-12 04:43:21 |
合計ジャッジ時間 | 2,403 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
import syssys.setrecursionlimit(1000000000)N = int(input())memo1 = [ -1 for i in range(N+1)]memo2 = [ -1 for i in range(N+1)]memo3 = [ -1 for i in range(N+1)]MOD = 10**9 + 7def r1(n):if n == 1:return 1elif n == 2:return 0elif n == 3:return 1else:if memo2[n-1] == -1:memo2[n-1] = r2(n-1) % MODif memo3[n-1] == -1:memo3[n-1] = r3(n-1)%MODreturn (memo2[n-1] + memo3[n-1]) % MODdef r2(n):if n == 1:return 0elif n == 2:return 1elif n == 3:return 1else:if memo1[n-2] == -1:memo1[n-2] = r1(n-2) % MODif memo3[n-2] == -1:memo3[n-2] = r3(n-2) % MODreturn (memo1[n-2] + memo3[n-2]) % MODdef r3(n):if n == 1:return 0elif n == 2:return 0elif n == 3:return 1else:if memo1[n-3] == -1:memo1[n-3] = r1(n-3) % MODif memo2[n-3] == -1:memo2[n-3] = r2(n-3) % MODreturn (memo1[n-3] + memo2[n-3]) % MODdef r(n):return (r1(n) + r2(n) + r3(n)) % MODfor i in range(4,N):r(i)print(r(N))