結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー テナガザル
提出日時 2025-11-28 22:56:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 420 ms / 3,000 ms
コード長 885 bytes
コンパイル時間 1,246 ms
コンパイル使用メモリ 107,848 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-11-28 22:57:02
合計ジャッジ時間 11,303 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  const int mod = 998244353;
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  sort(a.begin(), a.end());
  vector<long long> dp(n + 1, 1);
  dp[n] = 0;
  vector<int> l(n), r(n);
  for (int i = 0; i < n; ++i)
  {
    l[i] = lower_bound(a.begin(), a.end(), a[i] - k) - a.begin();
    r[i] = upper_bound(a.begin(), a.end(), a[i] + k) - a.begin();
  }
  for (int i = 1; i < m; ++i)
  {
    vector<long long> ndp(n + 1);
    for (int j = 0; j < n; ++j)
    {
      ndp[l[j]] += dp[j];
      ndp[r[j]] -= dp[j];
    }
    for (int j = 0; j < n; ++j) ndp[j + 1] += ndp[j];
    swap(ndp, dp);
    for (int j = 0; j <= n; ++j) dp[j] %= mod;
  }
  long long ans = 0;
  for (int i = 0; i < n; ++i) ans = (ans + dp[i]) % mod;
  cout << ans << endl;
}
0