結果
問題 | No.3052 Increasing Sliding Window Minimum |
ユーザー |
![]() |
提出日時 | 2025-03-07 23:23:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 685 ms / 2,000 ms |
コード長 | 1,085 bytes |
コンパイル時間 | 454 ms |
コンパイル使用メモリ | 82,972 KB |
実行使用メモリ | 82,564 KB |
最終ジャッジ日時 | 2025-03-07 23:23:35 |
合計ジャッジ時間 | 12,928 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 42 |
ソースコード
mod = 998244353 def solve(): n = int(input()) A = list(map(int, input().split())) A += [-1, -1, -1, -1, -1] Q = [0 for _ in range(n + 1)] U = [0 for _ in range(n + 5)] C = [0 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 C[i] += 1 dp = [0 for _ in range(n + 10)] dp[0] = 1 for i in range(1, n + 1): ndp = [0 for _ in range(n + 10)] if Q[i] == 0: for j in range(n + 1): r = j - i + 1 - C[j] if r > 0: ndp[j] = (ndp[j] + dp[j] * r) % mod if U[j + 1] == 0: ndp[j + 1] = (ndp[j + 1] + dp[j]) % mod if U[j + 2] == 0: ndp[j + 2] = (ndp[j + 2] + dp[j]) % mod else: j = Q[i] C[j] -= 1 ndp[j] = (ndp[j] + dp[j - 2] + dp[j - 1]) % mod for k in range(j + 1, n + 1): C[k] -= 1 ndp[k] = (ndp[k] + dp[k]) % mod dp = ndp[:] ans = 0 for i in range(1, n + 1): ans = (ans + dp[i]) % mod print(ans) return for _ in range(int(input())): solve()