結果
問題 | No.385 カップ麺生活 |
ユーザー | 明智重蔵 |
提出日時 | 2016-07-03 11:10:22 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 213 ms / 2,000 ms |
コード長 | 2,976 bytes |
コンパイル時間 | 1,001 ms |
コンパイル使用メモリ | 118,376 KB |
実行使用メモリ | 33,568 KB |
最終ジャッジ日時 | 2024-04-15 07:31:09 |
合計ジャッジ時間 | 4,363 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 34 ms
25,620 KB |
testcase_01 | AC | 34 ms
25,240 KB |
testcase_02 | AC | 34 ms
25,356 KB |
testcase_03 | AC | 34 ms
25,476 KB |
testcase_04 | AC | 50 ms
31,744 KB |
testcase_05 | AC | 35 ms
25,480 KB |
testcase_06 | AC | 52 ms
31,748 KB |
testcase_07 | AC | 56 ms
31,508 KB |
testcase_08 | AC | 37 ms
27,628 KB |
testcase_09 | AC | 32 ms
25,556 KB |
testcase_10 | AC | 213 ms
31,548 KB |
testcase_11 | AC | 33 ms
25,364 KB |
testcase_12 | AC | 44 ms
31,864 KB |
testcase_13 | AC | 72 ms
29,588 KB |
testcase_14 | AC | 177 ms
31,548 KB |
testcase_15 | AC | 80 ms
29,604 KB |
testcase_16 | AC | 35 ms
25,628 KB |
testcase_17 | AC | 102 ms
33,568 KB |
testcase_18 | AC | 40 ms
29,560 KB |
testcase_19 | AC | 39 ms
29,828 KB |
testcase_20 | AC | 55 ms
31,628 KB |
testcase_21 | AC | 157 ms
31,680 KB |
testcase_22 | AC | 72 ms
31,628 KB |
testcase_23 | AC | 151 ms
29,756 KB |
testcase_24 | AC | 130 ms
27,688 KB |
testcase_25 | AC | 34 ms
25,496 KB |
testcase_26 | AC | 34 ms
27,404 KB |
testcase_27 | AC | 100 ms
29,372 KB |
testcase_28 | AC | 86 ms
31,556 KB |
testcase_29 | AC | 49 ms
29,712 KB |
testcase_30 | AC | 115 ms
31,536 KB |
testcase_31 | AC | 34 ms
27,408 KB |
testcase_32 | AC | 36 ms
25,616 KB |
testcase_33 | AC | 84 ms
29,592 KB |
testcase_34 | AC | 38 ms
31,644 KB |
コンパイルメッセージ
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.Linq; //No.385 カップ麺生活 class Program { static string InputPattern = "InputX"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("100"); WillReturn.Add("2"); WillReturn.Add("47 50"); //5 } else if (InputPattern == "Input2") { WillReturn.Add("500"); WillReturn.Add("5"); WillReturn.Add("111 222 333 444 555"); //8 } else if (InputPattern == "Input3") { WillReturn.Add("2447"); WillReturn.Add("3"); WillReturn.Add("9 6 10"); //79842 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List<string> InputList = GetInputList(); int M = int.Parse(InputList[0]); Eratosthenes(M); int[] CArr = InputList[2].Split(' ').Select(X => int.Parse(X)).ToArray(); Array.Sort(CArr); //昇順にソートしておく //最大購入数[残金]なDP表 var DPArr = new Nullable<int>[M + 1]; DPArr[M] = 0; foreach (int EachCost in CArr) { for (int I = M; 0 <= I; I--) { if (DPArr[I].HasValue == false) continue; int NewInd = I - EachCost; if (NewInd < 0) break; int NewVal = DPArr[I].Value + 1; if (DPArr[NewInd].HasValue == false || DPArr[NewInd].Value < NewVal) { DPArr[NewInd] = NewVal; } } } int Answer = 0; //残金が素数の購入数を集計 for (int I = 0; I <= M; I++) { if (DPArr[I].HasValue == false) continue; if (SosuuArr.Contains(I) == false) continue; Answer += DPArr[I].Value; } //最大の購入数を加算 Answer += DPArr.Max(X => X ?? 0); Console.WriteLine(Answer); } static int[] SosuuArr; //エラトステネスの篩 static void Eratosthenes(int pJyougen) { var CheckArr = new System.Collections.BitArray(pJyougen + 1); for (int I = 2; I <= CheckArr.Count - 1; I++) { CheckArr[I] = true; } for (int I = 2; I <= CheckArr.Count - 1; I++) { if (I != 2 && I % 2 == 0) continue; if (CheckArr[I]) { for (int J = I * 2; J <= CheckArr.Count - 1; J += I) { CheckArr[J] = false; } } } var SosuuList = new List<int>(); for (int I = 2; I <= CheckArr.Count - 1; I++) if (CheckArr[I]) SosuuList.Add(I); SosuuArr = SosuuList.ToArray(); } }