結果
| 問題 |
No.527 ナップサック容量問題
|
| ユーザー |
 14番
|
| 提出日時 | 2017-06-09 23:28:13 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,714 bytes |
| コンパイル時間 | 2,477 ms |
| コンパイル使用メモリ | 115,924 KB |
| 実行使用メモリ | 132,488 KB |
| 最終ジャッジ日時 | 2024-09-22 19:14:19 |
| 合計ジャッジ時間 | 10,706 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 WA * 17 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
public class Program
{
public void Proc()
{
int inputCount = int.Parse(Reader.ReadLine());
for (int i = 0; i < inputCount; i++) {
int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
this.NimotsuList.Add(new Nimotu(inpt[0], inpt[1]));
}
int target = int.Parse(Reader.ReadLine());
this.NimotsuList = this.NimotsuList.OrderBy(a => a.Value).ToList();
long tmp1 = GetAns(0, target);
long tmp2 = 1;
if(tmp1 == 0) {
long tmp = GetAns3(0, target);
if(tmp == target || tmp <= 0) {
tmp1 = 1;
tmp2 = this.NimotsuList.Min(a => a.Size - 1);
} else {
tmp1 = GetAns2(0, tmp) + 1;
tmp = GetAns4(0, tmp);
if(tmp <= 0) {
tmp2 = this.NimotsuList.Sum(a => a.Size);
} else {
tmp2 = GetAns(0, tmp) - 1;
}
}
} else {
long tmp = GetAns4(0, target);
if(tmp == target || tmp < 0) {
tmp2 = NimotsuList.Sum(a => a.Size);
} else {
tmp2 = GetAns(0, tmp) - 1;
}
}
Console.WriteLine(tmp1);
if(tmp2 == this.NimotsuList.Sum(a=>a.Size)) {
Console.WriteLine("inf");
} else {
Console.WriteLine(tmp2);
}
}
private Dictionary<int, Dictionary<long, long>> dic = new Dictionary<int, Dictionary<long, long>>();
private Dictionary<int, Dictionary<long, long>> dic2 = new Dictionary<int, Dictionary<long, long>>();
private Dictionary<int, Dictionary<long, long>> dic3 = new Dictionary<int, Dictionary<long, long>>();
private Dictionary<int, Dictionary<long, long>> dic4 = new Dictionary<int, Dictionary<long, long>>();
private long GetAns4(int idx, long remain)
{
if (remain < 0)
{
return 0;
}
if (idx >= this.NimotsuList.Count)
{
if (remain < 0)
{
return 0;
}
return -1;
}
if (!dic4.ContainsKey(idx))
{
dic4.Add(idx, new Dictionary<long, long>());
}
if (dic4[idx].ContainsKey(remain))
{
return dic4[idx][remain];
}
long ans = long.MaxValue;
long tmp;
tmp = GetAns4(idx + 1, remain - NimotsuList[idx].Value);
if (tmp >= 0)
{
ans = Math.Min(ans, tmp + NimotsuList[idx].Value);
}
tmp = GetAns4(idx + 1, remain);
if (tmp >= 0)
{
ans = Math.Min(ans, tmp);
}
if(ans == long.MaxValue) {
ans = -1;
}
dic4[idx][remain] = ans;
return ans;
}
private long GetAns3(int idx, long remain) {
if (remain <= 0)
{
return -1;
}
if (idx >= this.NimotsuList.Count)
{
if (remain <= 0)
{
return -1;
}
return 0;
}
if (!dic3.ContainsKey(idx))
{
dic3.Add(idx, new Dictionary<long, long>());
}
if (dic3[idx].ContainsKey(remain))
{
return dic3[idx][remain];
}
long ans = 0;
long tmp;
if (this.NimotsuList[idx].Value < remain)
{
tmp = GetAns3(idx + 1, remain - NimotsuList[idx].Value);
if (tmp >= 0)
{
ans = Math.Max(ans, tmp + NimotsuList[idx].Value);
}
}
tmp = GetAns3(idx + 1, remain);
if (tmp >= 0)
{
ans = Math.Max(ans, tmp);
}
dic3[idx][remain] = ans;
return ans;
}
private long GetAns2(int idx, long remain) {
if (remain == 0)
{
return 0;
}
if (idx >= this.NimotsuList.Count)
{
return -1;
}
if (!dic2.ContainsKey(idx))
{
dic2.Add(idx, new Dictionary<long, long>());
}
if (dic2[idx].ContainsKey(remain))
{
return dic2[idx][remain];
}
long ans = 0;
long tmp;
if (this.NimotsuList[idx].Value <= remain)
{
tmp = GetAns2(idx + 1, remain - NimotsuList[idx].Value);
if (tmp >= 0)
{
ans = Math.Max(ans, tmp + NimotsuList[idx].Size);
}
}
tmp = GetAns2(idx + 1, remain);
if (tmp >= 0)
{
ans = Math.Max(ans, tmp);
}
dic2[idx][remain] = ans;
return ans;
}
private long GetAns(int idx, long remain) {
if(remain == 0) {
return 0;
}
if (idx >= this.NimotsuList.Count)
{
return -1;
}
if(!dic.ContainsKey(idx)) {
dic.Add(idx, new Dictionary<long, long>());
}
if(dic[idx].ContainsKey(remain)) {
return dic[idx][remain];
}
long ans = long.MaxValue;
long tmp;
if(this.NimotsuList[idx].Value <= remain) {
tmp = GetAns(idx + 1, remain - NimotsuList[idx].Value);
if(tmp >= 0) {
ans = Math.Min(ans, tmp + NimotsuList[idx].Size);
}
}
tmp = GetAns(idx + 1, remain);
if (tmp >= 0)
{
ans = Math.Min(ans, tmp);
}
if(ans == long.MaxValue) {
ans = -1;
}
dic[idx][remain] = ans;
return ans;
}
private List<Nimotu> NimotsuList = new List<Nimotu>();
private class Nimotu {
public long Value;
public long Size;
public Nimotu(int val, int size) {
this.Value = val;
this.Size = size;
}
}
public class Reader
{
private static StringReader sr;
public static bool IsDebug = false;
public static string ReadLine()
{
if (IsDebug)
{
if (sr == null)
{
sr = new StringReader(InputText.Trim());
}
return sr.ReadLine();
}
else
{
return Console.ReadLine();
}
}
private static string InputText = @"
2
33 4
114 514
147
";
}
public static void Main(string[] args)
{
#if DEBUG
Reader.IsDebug = true;
#endif
Program prg = new Program();
prg.Proc();
}
}