結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー tobisatis
提出日時 2025-11-01 18:05:35
言語 C#
(.NET 8.0.404)
結果
WA  
実行時間 -
コード長 1,469 bytes
コンパイル時間 16,678 ms
コンパイル使用メモリ 169,832 KB
実行使用メモリ 189,792 KB
最終ジャッジ日時 2025-11-01 18:06:05
合計ジャッジ時間 19,699 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 72 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /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 # 

#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

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

var n = I<int>();
var h = I<int>();
var vz = Range(n, I<int>);
var wz = Range(n, I<int>);

Array.Reverse(vz);
Array.Reverse(wz);

var min = int.MinValue / 2;
var dp = new (int, int)[n + 1, h + 1];
for (var i = 0; i <= n; i++) for (var j = 0; j <= h; j++) dp[i, j] = (min, -1);
dp[0, 0] = (0, -1);
for (var i = 0; i < n; i++)
{
    for (var j = 0; j <= h; j++) dp[i + 1, j] = dp[i, j];
    var v = vz[i];
    var w = wz[i];
    for (var j = 0; j <= h; j++)
    {
        var nv = v + dp[i, j].Item1;
        var nw = j + w;
        if (nw > h) break;
        var (cv, ci) = dp[i + 1, nw];
        if (cv < nv || (cv == nv && ci > i)) dp[i + 1, nw] = (nv, i);
    }
}
var maxv = -1;
var maxi = int.MinValue;
var curw = -1;
for (var i = 0; i <= h; i++)
{
    var (v, k) = dp[n, i];
    if (maxv < v) (maxv, maxi, curw) = (v, k, i);
    else if (maxv == v && k > maxi) (maxi, curw) = (k, i);
}
var ans = new List<int>();
var z = n;
while (true)
{
    var (_, k) = dp[z, curw];
    if (k < 0) break;
    ans.Add(n - k);
    z = k;
    curw -= wz[k];
}
Console.WriteLine(ans.Count);
Console.WriteLine(string.Join(' ', ans));
0