using System; using System.Collections.Generic; using System.Linq; // No.3329 Only the Rightest Choice is Right!!! // https://yukicoder.me/problems/no/3329 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("4 5"); WillReturn.Add("1 4 2 3"); WillReturn.Add("1 4 2 3"); //2 //3 4 } else if (InputPattern == "Input2") { WillReturn.Add("6 3000"); WillReturn.Add("1 1 1 1 1 1"); WillReturn.Add("3000 3000 3000 3000 3000 3000"); //1 //6 } else if (InputPattern == "Input3") { WillReturn.Add("10 3000"); WillReturn.Add("2992 3000 1 1 1 1 1 1 1 1"); WillReturn.Add("2992 3000 1 1 1 1 1 1 1 1"); //1 //2 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static long[] GetSplitArr(string pStr) { return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray(); } struct ItemInfoDef { internal long Score; internal long Weight; } static ItemInfoDef[] mItemInfoArr; static long UB; static long mWeightLimit; static void Main() { List InputList = GetInputList(); long[] wkArr = GetSplitArr(InputList[0]); mWeightLimit = wkArr[1]; long[] ValueArr = GetSplitArr(InputList[1]); long[] WeightArr = GetSplitArr(InputList[2]); var ItemInfoList = new List(); for (long I = 0; I <= ValueArr.GetUpperBound(0); I++) { ItemInfoDef WillAdd; WillAdd.Score = ValueArr[I]; WillAdd.Weight = WeightArr[I]; ItemInfoList.Add(WillAdd); } mItemInfoArr = ItemInfoList.ToArray(); UB = mItemInfoArr.GetUpperBound(0); // スコア[重さ][どこまでみたか]なインラインDPのDict var DPArrDict1 = new Dictionary(); DPArrDict1[UB] = new long?[mWeightLimit + 1]; DPArrDict1[UB][0] = 0; // 最後に選んだ品物[重さ][どこまでみたか]なインラインDP表 var DPArrDict2 = new Dictionary(); DPArrDict2[UB] = new long?[mWeightLimit + 1]; for (long I = UB; 0 <= I; I--) { long?[] CurrArr1 = DPArrDict1[I]; long?[] CurrArr2 = DPArrDict2[I]; for (long J = mWeightLimit; 0 <= J; J--) { if (CurrArr1[J].HasValue == false) continue; long NewJ = J + mItemInfoArr[I].Weight; if (NewJ > mWeightLimit) continue; long NewScore = CurrArr1[J].Value + mItemInfoArr[I].Score; if (CurrArr1[NewJ].HasValue) { if (CurrArr1[NewJ].Value > NewScore) { continue; } if (CurrArr1[NewJ].Value == NewScore) { if (CurrArr2[NewJ].HasValue) { if (CurrArr2[NewJ] > I) { continue; } } } } CurrArr1[NewJ] = NewScore; CurrArr2[NewJ] = I; } if (0 < I) { DPArrDict1[I - 1] = (long?[])DPArrDict1[I].Clone(); DPArrDict2[I - 1] = (long?[])DPArrDict2[I].Clone(); } } //for (long I = UB; 0 <= I; I--) { // Console.WriteLine("{0}まで見たDP結果", I); // long?[] CurrArr1 = DPArrDict1[I]; // for (long J = 0; J <= mWeightLimit; J++) { // if (CurrArr1[J].HasValue) { // Console.WriteLine("CurrArr1[{0}]={1}", J, CurrArr1[J]); // } // } // long?[] CurrArr2 = DPArrDict2[I]; // for (long J = 0; J <= mWeightLimit; J++) { // if (CurrArr2[J].HasValue) { // Console.WriteLine("CurrArr2[{0}]={1}", J, CurrArr2[J]); // } // } //} long CurrInd = 0; long RestWeight = mWeightLimit; var AnswerList = new List(); while (true) { bool HasAnswer = false; long AnswerItem = -1; long MaxScore = long.MinValue; for (long I = 0; I <= RestWeight; I++) { long?[] CurrArr1 = DPArrDict1[CurrInd]; long?[] CurrArr2 = DPArrDict2[CurrInd]; if (CurrArr1[I].HasValue == false) continue; if (CurrArr1[I].Value == 0) continue; if (MaxScore > CurrArr1[I].Value) continue; if (MaxScore == CurrArr1[I]) { if (AnswerItem > CurrArr2[I]) { continue; } } HasAnswer = true; MaxScore = CurrArr1[I].Value; AnswerItem = CurrArr2[I].Value; } if (HasAnswer == false) { break; } RestWeight -= mItemInfoArr[AnswerItem].Weight; AnswerList.Add(AnswerItem); CurrInd = AnswerItem + 1; if (CurrInd > UB) break; } Console.WriteLine(AnswerList.Count); for (int I = 0; I <= AnswerList.Count - 1; I++) { AnswerList[I]++; } Console.WriteLine(LongEnumJoin(" ", AnswerList)); } // セパレータとLong型の列挙を引数として、結合したstringを返す static string LongEnumJoin(string pSeparater, IEnumerable pEnum) { string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString()); return string.Join(pSeparater, StrArr); } }