結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー LyricalMaestro
提出日時 2025-11-29 12:40:30
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,282 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 317 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 272,648 KB
最終ジャッジ日時 2025-11-29 12:40:39
合計ジャッジ時間 8,916 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3391

MOD = 998244353

from collections  import deque


def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))

    a_map = {}
    for a in A:
        if a not in a_map:
            a_map[a] = 0
        a_map[a] += 1
    
    if M == 1:
        print(len(a_map))
        return 
    
    # 半分全列挙
    a_array = [(a, a_num) for a, a_num in a_map.items()]
    a_array.sort(key=lambda a : a[0])

    dp = a_array.copy()
    for _ in range(1, M):
        new_dp = []

        queue = deque()
        sums = 0
        dp_index = 0
        for a, a_num in a_array:
            while len(queue) > 0 and queue[0][0] < a - K:
                x, x_val = queue.popleft()
                sums -= x_val
                sums %= MOD
            while dp_index < len(dp) and dp[dp_index][0] <= a + K:
                x, x_val = dp[dp_index]
                queue.append((x, x_val))
                sums += x_val
                sums %= MOD
                dp_index += 1
            
            ans = (sums * a_num) % MOD
            new_dp.append((a, ans))
        dp = new_dp
    answer = 0
    for _, v in dp:
        answer += v
        answer %= MOD
    print(answer)






if __name__ == "__main__":
    main()
0