結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー i_taku
提出日時 2025-12-03 15:31:51
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,740 ms / 3,000 ms
コード長 859 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 480 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 87,804 KB
最終ジャッジ日時 2025-12-03 15:32:32
合計ジャッジ時間 40,255 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
def calc_l(i):
    ok = i
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if A[i] - A[mid] <= K:
            ok = mid
        else:
            ng = mid
    return ok
def calc_r(i):
    ok = i
    ng = N
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if A[mid] - A[i] <= K:
            ok = mid
        else:
            ng = mid
    return ok

mod = 998244353
L = [-1] * N
R = [-1] * N

for i in range(N):
    L[i] = calc_l(i)
    R[i] = calc_r(i)

dp = [1] * N
cum = [0] * (N + 1)
for i in range(N):
    cum[i + 1] = cum[i] + 1

for _ in range(M - 1):
    ndp = [0] * N
    for i in range(N):
        ndp[i] = cum[R[i] + 1] - cum[L[i]] % mod
    dp = ndp[:]
    for i in range(N):
        cum[i + 1] = (cum[i] + dp[i]) % mod
print(cum[-1])
0