結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2016-05-15 00:28:54 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 398 ms / 2,000 ms |
コード長 | 1,903 bytes |
コンパイル時間 | 2,511 ms |
コンパイル使用メモリ | 105,728 KB |
実行使用メモリ | 26,624 KB |
最終ジャッジ日時 | 2024-10-06 02:54:00 |
合計ジャッジ時間 | 4,282 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Text; using System.Linq; class Program { public void Proc() { Reader.IsDebug = false; int itemCount = int.Parse(Reader.ReadLine()); for (int i = 0; i < itemCount; i++) { this.priceList.Add(int.Parse(Reader.ReadLine())); } int ans = this.GetAns(this.priceList, 0); Console.WriteLine(ans); } private Dictionary<string, int> dic = new Dictionary<string, int>(); private int GetAns(List<int> target, int nebiki) { string key = string.Join("#", target); if (dic.ContainsKey(key)) { return dic[key]; } if (target.Count == 1) { return Math.Max(0, target[0] - nebiki); } int ans = int.MaxValue ; for (int i = 0; i < target.Count; i++) { List<int> subList = new List<int>(target); subList.RemoveAt(i); ans = Math.Min(ans, this.GetAns(subList, (nebiki + target[i]) % 1000) + (Math.Max(0, target[i] - nebiki))); } dic.Add(key, ans); return ans; } public List<int> priceList = new List<int>(); public class Reader { public static bool IsDebug = true; private static String PlainInput = @" 5 10000 1000 100 10 1 "; private static System.IO.StringReader Sr = null; public static string ReadLine() { if (IsDebug) { if (Sr == null) { Sr = new System.IO.StringReader(PlainInput.Trim()); } return Sr.ReadLine(); } else { return Console.ReadLine(); } } } static void Main() { Program prg = new Program(); prg.Proc(); } }