結果

問題 No.1720 Division Permutation
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:46:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 948 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 81,396 KB
実行使用メモリ 131,648 KB
最終ジャッジ日時 2025-04-16 16:49:39
合計ジャッジ時間 7,150 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

n, k = map(int, input().split())
p = list(map(int, input().split()))

dp = [[0] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 1

for x in range(1, k + 1):
    for i in range(1, n + 1):
        current_sum = 0
        max_deque = []
        min_deque = []
        for j in range(i - 1, -1, -1):
            current_val = p[j]
            while max_deque and p[max_deque[-1]] <= current_val:
                max_deque.pop()
            max_deque.append(j)
            while min_deque and p[min_deque[-1]] >= current_val:
                min_deque.pop()
            min_deque.append(j)
            current_max = p[max_deque[0]]
            current_min = p[min_deque[0]]
            if current_max - current_min + 1 == i - j:
                current_sum += dp[x - 1][j]
                if current_sum >= MOD:
                    current_sum -= MOD
        dp[x][i] = current_sum % MOD

for x in range(1, k + 1):
    print(dp[x][n] % MOD)
0