結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー tobisatis
提出日時 2025-11-28 22:18:46
言語 C#
(.NET 8.0.404)
結果
MLE  
実行時間 -
コード長 1,211 bytes
コンパイル時間 13,267 ms
コンパイル使用メモリ 171,228 KB
実行使用メモリ 221,624 KB
最終ジャッジ日時 2025-11-28 22:19:33
合計ジャッジ時間 44,332 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 MLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (103 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
raw source code 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

const int Mod = 998244353;

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

var n = I<int>();
var m = I<int>();
var k = I<int>();
var az = Range(n, I<int>);

Array.Sort(az);
var lz = new int[n];
var rz = new int[n];
lz.AsSpan().Fill(n + 1);
rz.AsSpan().Fill(-1);
for (var i = 0; i < n; i++)
{
    var a = az[i];
    for (var j = 0; j < n; j++)
    {
        if (Math.Abs(a - az[j]) > k) continue;
        lz[i] = Math.Min(lz[i], j);
        rz[i] = Math.Max(rz[i], j);
    }
}
var dp = new long[n];
dp.AsSpan().Fill(1);
var sp = new long[n + 1];
for (var i = 1; i <= n; i++) sp[i] = i;
for (var _lp = 1; _lp < m; _lp++)
{   
    var ep = new long[n];
    for (var i = 0; i < n; i++)
    {
        var (l, r) = (lz[i], rz[i]);
        ep[i] = (sp[r + 1] - sp[l] + Mod) % Mod;
    }
    dp = ep;
    for (var i = 1; i <= n; i++) sp[i] = (sp[i - 1] + dp[i - 1]) % Mod;
}
var ans = sp[n];
Console.WriteLine(ans);
0