結果
問題 |
No.3052 Increasing Sliding Window Minimum
|
ユーザー |
![]() |
提出日時 | 2025-03-07 23:06:40 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,131 bytes |
コンパイル時間 | 427 ms |
コンパイル使用メモリ | 82,968 KB |
実行使用メモリ | 544,396 KB |
最終ジャッジ日時 | 2025-03-07 23:07:00 |
合計ジャッジ時間 | 19,938 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 WA * 29 MLE * 9 |
ソースコード
mod = 998244353 def solve(): n = int(input()) A = list(map(int, input().split())) Q = [0 for _ in range(n + 1)] U = [0 for _ in range(n + 5)] C = [[0 for _ in range(n + 1)] for _ in range(n + 1)] for i in range(1, n + 1): C[i] = C[i - 1][:] a = A[i - 1] if a == -1: continue Q[a] = i U[i] = 1 for j in range(a): C[i][j] += 1 dp = [[0 for _ in range(n + 10)] for _ in range(n + 1)] dp[0][0] = 1 for i in range(1, n + 1): if Q[i] == 0: for j in range(i - 1, n + 1): r = j - i + 1 - C[i - 1][j] if r > 0: dp[i][j] = (dp[i][j] + dp[i - 1][j] * r) % mod if U[j + 1] == 0: dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j]) % mod if U[j + 2] == 0: dp[i][j + 2] = (dp[i][j + 2] + dp[i - 1][j]) % mod else: j = Q[i] dp[i][j] = (dp[i][j] + dp[i - 1][j - 2] + dp[i - 1][j - 1]) % mod for k in range(j + 1, n + 1): dp[i][k] = (dp[i][k] + dp[i - 1][k]) % mod ans = 0 for i in range(1, n + 1): ans = (ans + dp[n][i]) % mod print(ans) return for _ in range(int(input())): solve()