結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
![]() |
提出日時 | 2017-06-10 00:07:40 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,505 bytes |
コンパイル時間 | 1,006 ms |
コンパイル使用メモリ | 115,188 KB |
実行使用メモリ | 69,520 KB |
最終ジャッジ日時 | 2024-09-22 20:37:01 |
合計ジャッジ時間 | 7,754 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 WA * 25 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Text; using System.Linq; using System.Collections.Generic; class Program { private static readonly Scanner sc = new Scanner(); static void Main(string[] args) { int n = sc.Int; int[] vn = new int[101]; int[] wn = new int[101]; for (int i = 1; i <= n; i++) { vn[i] = sc.Int; wn[i] = sc.Int; } int v = sc.Int; int[][] dp = new int[101][]; for (int i = 0; i <= 100; i++) dp[i] = new int[100001]; for (int i = 1; i <= 100; i++) { for (int j = 1; j <= 100000; j++) { if (j < vn[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.Max(dp[i - 1][j], dp[i - 1][j - vn[i]] + wn[i]); } } if (dp[n][v] == 0) { int minw = 1000000000; for (int i = 1; i <= n; i++) minw = Math.Min(minw, wn[i]); Console.WriteLine(1); Console.WriteLine(minw-1); } else { Console.WriteLine(dp[n][v]); if (dp[n][v] == dp[n][100000]) { Console.WriteLine("inf"); } else { for (int i = 0; i < 100000; i++) { if (dp[n][v] < dp[n][i]) { Console.WriteLine(dp[n][i]-1); break; } } } } } } class Scanner { private string[] _str = new string[0]; private int _i; public string Line { get { return Console.ReadLine(); } } public string Str { get { if (_i >= _str.Length) { _str = Line.Split(' '); _i = 0; } return _str[_i++]; } } public string[] StrArr { get { return Line.Split(' '); } } public int Int { get { return int.Parse(Str); } } public int[] IntArr { get { return Line.Split(' ').Select(int.Parse).ToArray(); } } public long Long { get { return long.Parse(Str); } } public long[] LongArr { get { return Line.Split(' ').Select(long.Parse).ToArray(); } } public double Double { get { return double.Parse(Str); } } public double[] DoubleArr { get { return Line.Split(' ').Select(double.Parse).ToArray(); } } }