結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー LyricalMaestro
提出日時 2025-12-06 00:28:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,700 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 496 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 134,620 KB
最終ジャッジ日時 2025-12-06 00:28:48
合計ジャッジ時間 8,236 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 3 TLE * 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
    
    # 座標圧縮
    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]]

    cum_dp = [0] * value_max
    cum_d = 0
    for i in range(value_max):
        cum_d += dp[i]
        cum_d %= MOD
        cum_dp[i] = cum_d

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

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

            



    




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