結果
| 問題 | No.258 回転寿司(2) |
| ユーザー |
 明智重蔵
|
| 提出日時 | 2015-08-01 20:57:27 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 3,450 bytes |
| コンパイル時間 | 1,703 ms |
| コンパイル使用メモリ | 108,544 KB |
| 実行使用メモリ | 50,840 KB |
| 最終ジャッジ日時 | 2024-05-03 10:47:54 |
| 合計ジャッジ時間 | 7,660 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
コンパイルメッセージ
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;
class Program
{
static string InputPattern = "Input5";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4");
WillReturn.Add("1 2 3 4");
//6
//2 4
//お寿司の取り方は、
//「1個目と3個目」のお寿司を取る、
//「1個目と4個目」のお寿司を取る、
//または「2個目と4個目」のお寿司を取る方法があるが、
//2個目、4個目のお寿司を取ることで、最大の美味しさが得られる。
}
else if (InputPattern == "Input2") {
WillReturn.Add("4");
WillReturn.Add("5 4 4 9");
//14
//1 4
//1個目のお寿司と4個目のお寿司を取ることで最大の美味しさの合計が得られる。
}
else if (InputPattern == "Input3") {
WillReturn.Add("7");
WillReturn.Add("1 2 9 10 1 1 4");
//16
//2 4 7
//2,10,4と取れば最大の16が得られる。
//10の後の6番目の１をあえてスルーしないといけない。
}
else if (InputPattern == "Input4") {
WillReturn.Add("1");
WillReturn.Add("100");
//100
//1
//1皿しかない場合もあります。
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct JyoutaiDef
{
internal int CurrP;
internal int SumVal;
internal List<int> SelectSushiList;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] VArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
int UB = VArr.GetUpperBound(0);
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrP = 0;
WillPush.SumVal = 0;
WillPush.SelectSushiList = new List<int>();
stk.Push(WillPush);
int AnswerSum = 0;
var AnswerSelectSushiList = new List<int>();
//メモ化探索用
var MemoDict = new Dictionary<int, int>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (AnswerSum < Popped.SumVal) {
AnswerSum = Popped.SumVal;
AnswerSelectSushiList = Popped.SelectSushiList;
}
for (int I = Popped.CurrP; I <= UB && I <= Popped.CurrP + 1; I++) {
WillPush.CurrP = I + 2;
WillPush.SumVal = Popped.SumVal + VArr[I];
WillPush.SelectSushiList = new List<int>(Popped.SelectSushiList) { I + 1 };
if (MemoDict.ContainsKey(WillPush.CurrP)) {
if (MemoDict[WillPush.CurrP] >= WillPush.SumVal)
continue;
}
MemoDict[WillPush.CurrP] = WillPush.SumVal;
stk.Push(WillPush);
}
}
Console.WriteLine(AnswerSum);
var sb = new System.Text.StringBuilder();
AnswerSelectSushiList.ForEach(X => sb.AppendFormat("{0} ", X));
Console.WriteLine(sb.ToString());
}
}