結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー norioc
提出日時 2026-01-03 00:43:04
言語 Python3
(3.14.2 + numpy 2.4.0 + scipy 1.16.3)
結果
TLE  
実行時間 -
コード長 1,177 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,118 ms
コンパイル使用メモリ 21,540 KB
実行使用メモリ 24,404 KB
最終ジャッジ日時 2026-01-03 00:43:11
合計ジャッジ時間 6,573 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from bisect import bisect_left, bisect_right
from itertools import accumulate


def find_interval(a: list, lo: int, hi: int) -> tuple[int, int, int]:
    """
    ソート済みリスト a の要素の lo 以上 hi 以下の個数と区間を返す
    return: 範囲内の個数, l, r
    """
    assert lo <= hi
    empty = 0, -1, -1  # 区間なし
    if not a or lo > a[-1] or hi < a[0]: return empty

    l = bisect_left(a, lo)
    r = bisect_right(a, hi) - 1
    if l > r: return empty
    return r-l+1, l, r


def mod_accum(a: list, mod: int):
    acc = list(accumulate(a, lambda a, b: (a + b) % mod))
    return lambda l, r: (acc[r] - (acc[l-1] if l > 0 else 0)) % mod


MOD = 998244353
N, M, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
l_inds = []
r_inds = []
for i in range(N):
    _, l, r = find_interval(A, A[i]-K, A[i]+K)
    l_inds.append(l)
    r_inds.append(r)

dp = [1] * N
for i in range(M-1):
    pp = [0] * N
    dp, pp = pp, dp
    acc_dp = mod_accum(pp, MOD)

    for j in range(N):
        dp[j] += acc_dp(l_inds[j], r_inds[j])
        dp[j] %= MOD

ans = 0
for i in range(N):
    ans += dp[i]
    ans %= MOD

print(ans)
0