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 void Main() { List InputList = GetInputList(); long[] wkArr = GetSplitArr(InputList[0]); long WeightLimit = 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); } ItemInfoDef[] ItemInfoArr = ItemInfoList.ToArray(); long UB = ItemInfoArr.GetUpperBound(0); // 状態[重さ]なインラインDP表 var DPDict = new Dictionary(); for (long I = UB; 0 <= I; I--) { Action UpdateAct = (pNewJyoutai, pNewWeight) => { if (WeightLimit < pNewWeight) return; if (DPDict.ContainsKey(pNewWeight)) { // スコアで劣る場合 if (DPDict[pNewWeight].Score > pNewJyoutai.Score) return; // 現在ItemIndで劣る場合 if (DPDict[pNewWeight].CurrItemInd > pNewJyoutai.CurrItemInd) return; } DPDict[pNewWeight] = pNewJyoutai; }; foreach (long EachKey in DPDict.Keys.ToArray().OrderByDescending(pX => pX)) { long NewWeight = EachKey + ItemInfoArr[I].Weight; if (NewWeight > WeightLimit) continue; JyoutaiDef CurrJyoutai = DPDict[EachKey]; JyoutaiDef NewJyoutai; NewJyoutai.Score = CurrJyoutai.Score + ItemInfoArr[I].Score; NewJyoutai.CurrItemInd = I; NewJyoutai.PrevWeight = EachKey; UpdateAct(NewJyoutai, NewWeight); } // 1つ目として取得する場合 JyoutaiDef FirstJyoutai; FirstJyoutai.Score = ItemInfoArr[I].Score; FirstJyoutai.CurrItemInd = I; FirstJyoutai.PrevWeight = -1; UpdateAct(FirstJyoutai, ItemInfoArr[I].Weight); } //foreach (var EachPair in DPDict.OrderBy(pX => pX.Key)) { // Console.WriteLine("Weight={0},Score={1},CurrItemInd={2},PrevWeight={3}", // EachPair.Key, EachPair.Value.Score, EachPair.Value.CurrItemInd, EachPair.Value.PrevWeight); //} // ---------------------------------------------------- // DPの復元パート // ---------------------------------------------------- var Tmp1 = DPDict.OrderByDescending(pX => pX.Value.Score); var Tmp2 = Tmp1.ThenByDescending(pX => pX.Value.CurrItemInd); long CurrWeight = Tmp2.First().Key; var AnswerList = new List(); while (true) { AnswerList.Add(1 + DPDict[CurrWeight].CurrItemInd); if (DPDict[CurrWeight].PrevWeight == -1) break; CurrWeight = DPDict[CurrWeight].PrevWeight; } Console.WriteLine(AnswerList.Count); Console.WriteLine(LongEnumJoin(" ", AnswerList)); } struct JyoutaiDef { internal long Score; internal long CurrItemInd; internal long PrevWeight; } // セパレータとLong型の列挙を引数として、結合したstringを返す static string LongEnumJoin(string pSeparater, IEnumerable pEnum) { string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString()); return string.Join(pSeparater, StrArr); } }