結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー Carpenters-Cat
提出日時 2025-11-28 22:59:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,318 ms / 3,000 ms
コード長 658 bytes
コンパイル時間 4,025 ms
コンパイル使用メモリ 255,660 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-28 22:59:54
合計ジャッジ時間 32,322 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
int main () {
	int N, M, K;
	cin >> N >> M >> K;
	std::vector<int> A(N);
	for (auto& a : A) cin >> a;
	sort(A.begin(), A.end());
	vector<mint> dp1(N, mint(0)), dp2(N, mint(1));
	for (int i = 1; i < M; i ++) {
		mint sum = 0;
		int l = 0, r = 0;
		for (int j = 0; j < N; j ++) {
			while (r < N && A[r] <= A[j] + K) {
				sum += dp2[r];
				r ++;
			}
			while (l < N && A[l] < A[j] - K) {
				sum -= dp2[l];
				l ++;
			}
			dp1[j] = sum;
		}
		swap(dp1, dp2);
	}
	cout << accumulate(dp2.begin(), dp2.end(), mint(0)).val() << endl;
}
0