結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー norioc
提出日時 2026-01-03 00:46:20
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
結果
AC  
実行時間 846 ms / 3,000 ms
コード長 1,683 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,473 ms
コンパイル使用メモリ 214,288 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-03 00:46:42
合計ジャッジ時間 21,962 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 998244353;

tuple<int,int,int> find_interval(const vector<long long>& a,
                                 long long lo, long long hi) {
    if (a.empty() || lo > a.back() || hi < a.front()) {
        return {0, -1, -1};
    }
    int l = lower_bound(a.begin(), a.end(), lo) - a.begin();
    int r = upper_bound(a.begin(), a.end(), hi) - a.begin() - 1;
    if (l > r) return {0, -1, -1};
    return {r - l + 1, l, r};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    sort(A.begin(), A.end());

    vector<int> l_inds(N), r_inds(N);
    for (int i = 0; i < N; i++) {
        auto [cnt, l, r] = find_interval(A, A[i] - K, A[i] + K);
        l_inds[i] = l;
        r_inds[i] = r;
    }

    vector<long long> dp(N, 1), pp(N);

    for (int iter = 0; iter < M - 1; iter++) {
        fill(pp.begin(), pp.end(), 0);
        swap(dp, pp);
        
        vector<long long> acc(N);
        acc[0] = pp[0] % MOD;
        for (int i = 1; i < N; i++) {
            acc[i] = (acc[i - 1] + pp[i]) % MOD;
        }

        for (int j = 0; j < N; j++) {
            int l = l_inds[j];
            int r = r_inds[j];
            if (l != -1) {
                long long val = acc[r];
                if (l > 0) val = (val - acc[l - 1] + MOD) % MOD;
                dp[j] = (dp[j] + val) % MOD;
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        ans = (ans + dp[i]) % MOD;
    }

    cout << ans << '\n';
    return 0;
}
0