結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー 回転
提出日時 2025-11-28 22:37:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,079 bytes
コンパイル時間 3,610 ms
コンパイル使用メモリ 291,124 KB
実行使用メモリ 16,204 KB
最終ジャッジ日時 2025-11-28 22:37:37
合計ジャッジ時間 8,142 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long
#define int long long
#define INF 1e18
#define MOD 998244353

int N,M,K;
int A[505050];
signed main(){
    cin >> N >> M >> K;
    for(int i = 0;i < N;i++)cin >> A[i];
    sort(A, A+N);

    unordered_map<int,int> now;
    for(int i = 0;i < N;i++)now[A[i]] += 1;

    for(int i = 0;i < M-1;i++){
      unordered_map<int,int> next;
      vector<int> key;
      for(auto i:now)key.emplace_back(i.first);
      sort(key.begin(),key.end());
      int l = 0;
      int r = 0;
      int S = 0;
      for (auto j:key){
        while(r < key.size() and j-K <= key[r] and key[r] <= j+K){
          S += now[key[r]];
          S %= MOD;
          r += 1;
        }

        while (l < key.size() and key[l] < j-K){
          S += MOD;
          S -= now[key[l]];
          S %= MOD;
          l += 1;
        }

        next[j] += S;
      }
      now.swap(next);
    }

    int ans = 0;
    for(auto i:now){
      ans += i.second;
      ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}
0