結果

問題 No.527 ナップサック容量問題
ユーザー 14番14番
提出日時 2017-06-09 23:24:44
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 5,589 bytes
コンパイル時間 2,268 ms
コンパイル使用メモリ 117,112 KB
実行使用メモリ 142,056 KB
最終ジャッジ日時 2024-09-22 19:06:23
合計ジャッジ時間 11,650 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
25,884 KB
testcase_01 AC 36 ms
25,364 KB
testcase_02 AC 39 ms
27,668 KB
testcase_03 AC 40 ms
27,792 KB
testcase_04 AC 35 ms
25,364 KB
testcase_05 AC 218 ms
57,108 KB
testcase_06 AC 820 ms
125,372 KB
testcase_07 WA -
testcase_08 AC 149 ms
45,432 KB
testcase_09 AC 38 ms
25,620 KB
testcase_10 WA -
testcase_11 AC 395 ms
76,392 KB
testcase_12 AC 249 ms
61,312 KB
testcase_13 AC 719 ms
112,704 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 40 ms
25,592 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 40 ms
28,044 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 37 ms
25,392 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 36 ms
23,348 KB
testcase_29 WA -
testcase_30 AC 40 ms
23,864 KB
testcase_31 AC 223 ms
55,624 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 43 ms
27,924 KB
testcase_36 AC 37 ms
25,624 KB
testcase_37 AC 42 ms
25,888 KB
testcase_38 AC 42 ms
25,748 KB
testcase_39 AC 41 ms
25,500 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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);
				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();
	}
}
0