結果

問題 No.527 ナップサック容量問題
コンテスト
ユーザー Risen
提出日時 2026-10-25 12:45:26
言語 C#
(.NET 10.0.403 + ACL)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
AC  
実行時間 145 ms / 2,000 ms
+ 215µs
コード長 1,413 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,119 ms
コンパイル使用メモリ 171,044 KB
実行使用メモリ 51,980 KB
最終ジャッジ日時 2026-10-25 12:45:45
合計ジャッジ時間 17,122 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge7_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (293 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

using System;
using System.Collections.Generic;
using System.Linq;

public static class Solution
{
    public static void Main()
    {
        var N = int.Parse(Console.ReadLine());
        var items = new (int v, int w)[N];
        for (int i = 0; i < N; i++)
        {
            var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            items[i] = (vals[0], vals[1]);
        }
        var V = int.Parse(Console.ReadLine());

        var nap = new Dictionary<int, int> { [0] = 0 };
        foreach (var item in items)
        {
            var adds = new List<(int v, int w)>();
            foreach (var kv in nap)
            {
                var w = kv.Key + item.w;
                var v = kv.Value + item.v;
                if (!nap.TryGetValue(w, out int value) || value < v)
                {
                    adds.Add((v, w));
                }
            }
            foreach (var add in adds)
            {
                if (!nap.TryGetValue(add.w, out int value) || value < add.v)
                {
                    nap[add.w] = add.v;
                }
            }
        }

        var ordered = nap.OrderBy(x => x.Key).ToArray();
        var min = Math.Max(ordered.First(x => x.Value == V).Key, 1);
        var max = ordered.FirstOrDefault(x => x.Value > V).Key - 1;
        Console.WriteLine(min);
        Console.WriteLine(max == -1 ? "inf" : max);
    }
}
0