結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー tobisatis
提出日時 2025-11-28 22:21:32
言語 C#
(.NET 8.0.404)
結果
MLE  
実行時間 -
コード長 1,247 bytes
コンパイル時間 11,450 ms
コンパイル使用メモリ 170,740 KB
実行使用メモリ 192,472 KB
最終ジャッジ日時 2025-11-28 22:23:51
合計ジャッジ時間 45,691 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 MLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (105 ミリ秒)。
  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 int[n];
var ep = new int[n];
dp.AsSpan().Fill(1);
var sp = new int[n + 1];
for (var i = 1; i <= n; i++) sp[i] = i;
for (var _lp = 1; _lp < m; _lp++)
{   
    for (var i = 0; i < n; i++)
    {
        var (l, r) = (lz[i], rz[i]);
        ep[i] = (sp[r + 1] - sp[l]) % Mod;
        if (ep[i] < 0) ep[i] += Mod;
    }
    (dp, ep) = (ep, dp);
    for (var i = 1; i <= n; i++) sp[i] = (sp[i - 1] + dp[i - 1]) % Mod;
}
var ans = sp[n];
Console.WriteLine(ans);
0