結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー LyricalMaestro
提出日時 2025-12-06 00:33:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,591 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 279 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 79,188 KB
最終ジャッジ日時 2025-12-06 00:33:30
合計ジャッジ時間 22,094 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 2 -- * 14
権限があれば一括ダウンロードができます

ソースコード

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
    
    # 座標圧縮
    value_set = set(a_map.keys())
    value_list = list(value_set)
    value_list.sort()
    value_map = {}
    for i, a in enumerate(value_list):
        value_map[a] = i
    value_max = len(value_list)

    dp = [0] * value_max
    for i in range(value_max):
        dp[i] = a_map[value_list[i]]
    
    b_map = [0] * value_max
    for i in range(value_max):
        b_map[i] = a_map[value_list[i]]
    a_map = b_map

    dp_sift = [dp, [0] * value_max]
    for idx in range(1, M):
        low_index = 0
        high_index = 0
        new_dp = dp_sift[idx % 2]
        cum_d = dp[0]
        for i in range(value_max):
            a0 = value_list[i]
            while low_index < i and a0 - value_list[low_index] > K:
                cum_d -= dp[low_index]
                cum_d %= MOD
                low_index += 1

            while high_index + 1 < value_max and value_list[high_index + 1] <= a0 + K:
                high_index += 1
                cum_d += dp[high_index]
                cum_d %= MOD
            
            new_dp[i] = (cum_d * a_map[i]) % MOD
        
        dp = new_dp
    
    answer = 0
    for i in range(value_max):
        answer += dp[i]
        answer %= MOD
    print(answer)

            



    




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