結果

問題 No.3052 Increasing Sliding Window Minimum
ユーザー とりゐ
提出日時 2025-03-07 23:55:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,029 ms / 2,000 ms
コード長 1,340 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 79,452 KB
最終ジャッジ日時 2025-03-07 23:55:26
合計ジャッジ時間 17,050 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353


def solve(n, a):
    inv = [-1] * n
    free = [0] * n
    for i in range(n):
        if a[i] != -1:
            inv[a[i]] = i
        else:
            free[i] = 1
        if i > 0:
            free[i] += free[i - 1]
    dp = [0] * (n + 1)
    dp[0] = 1
    cnt = 0
    for i in range(n):
        ndp = [0] * (n + 1)
        # 進める
        for j in range(n + 1):
            if j + 1 <= n:
                if inv[i] == -1 and a[j] == -1:
                    ndp[j + 1] += dp[j]
                elif a[j] == i:
                    ndp[j + 1] += dp[j]
            if j + 2 <= n:
                if inv[i] == -1 and a[j + 1] == -1:
                    ndp[j + 2] += dp[j]
                elif a[j + 1] == i:
                    ndp[j + 2] += dp[j]

        # 埋める
        for j in range(n + 1):
            if inv[i] != -1:
                if inv[i] < j:
                    ndp[j] += dp[j]
            elif j > 0:
                ndp[j] += dp[j] * ((max(0, free[j - 1] - cnt)))
        dp = [j % mod for j in ndp]
        if inv[i] == -1:
            cnt += 1
    return sum(dp) % mod


for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    A = []
    for i in a:
        if i > 0:
            A.append(i - 1)
        else:
            A.append(-1)
    print(solve(n, A))
0