結果
問題 |
No.2031 Colored Brackets
|
ユーザー |
![]() |
提出日時 | 2022-08-10 13:52:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 302 ms / 2,000 ms |
コード長 | 800 bytes |
コンパイル時間 | 265 ms |
コンパイル使用メモリ | 82,532 KB |
実行使用メモリ | 136,544 KB |
最終ジャッジ日時 | 2024-09-21 00:16:37 |
合計ジャッジ時間 | 6,365 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
def acum(List):#累積和 rev = [0 for _ in range(len(List))] for i in range(len(List)): if i == 0: rev[i] = List[i] else: rev[i] = rev[i-1] + List[i] return rev N = int(input()) S = [''] + list(input()) d = [0] for s in S[1:]: if s == '(': d += [1] else: d += [-1] d = acum(d) dp = [[0] *(N+1) for _ in range(N+1)] dp[0][0] = 1 mod = 998244353 for i in range(N): for r in range(N+1): if d[i+1]-r >= 0: dp[i+1][r] += dp[i][r] if S[i+1] == '(': if r + 1 <= N and d[i+1]-(r+1) >= 0: dp[i+1][r+1] += dp[i][r] else: if r -1 >= 0 and d[i+1]-(r-1) >= 0: dp[i+1][r-1] += dp[i][r] dp[i+1][r] %= mod ans = dp[N][0]%mod print(ans)