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 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); } mItemInfoArr = ItemInfoList.ToArray(); long UB = mItemInfoArr.GetUpperBound(0); var DPDictArr = new Dictionary[UB + 1]; for (long I = UB; 0 <= I; I--) { if (I < UB) { DPDictArr[I] = new Dictionary(DPDictArr[I + 1]); } else { DPDictArr[I] = new Dictionary(); } Action UpdateAct = (pNewScore, pWeightSum) => { if (pWeightSum > WeightLimit) return; bool IsOK = false; if (DPDictArr[I].ContainsKey(pWeightSum)) { if (DPDictArr[I][pWeightSum].Score < pNewScore) { IsOK = true; } else if (DPDictArr[I][pWeightSum].Score == pNewScore) { if (DPDictArr[I][pWeightSum].LastItemInd < I) { IsOK = true; } } } else { IsOK = true; } if (IsOK) { JyoutaiDef NewJyoutai; NewJyoutai.Score = pNewScore; NewJyoutai.LastItemInd = I; DPDictArr[I][pWeightSum] = NewJyoutai; } }; if (I < UB) { foreach (var EachPair in DPDictArr[I + 1]) { UpdateAct(EachPair.Value.Score + mItemInfoArr[I].Score, EachPair.Key + mItemInfoArr[I].Weight); } } UpdateAct(mItemInfoArr[I].Score, mItemInfoArr[I].Weight); } //for (long I = UB; 0 <= I; I--) { // Console.WriteLine("■■■{0}までのDB結果■■■", I); // foreach (var EachPair in DPDictArr[I]) { // Console.WriteLine("重さ={0},Score={1},LastItemInd={2}", // EachPair.Key, EachPair.Value.Score, EachPair.Value.LastItemInd); // } //} ExecDP(DPDictArr, WeightLimit); } // DP復元を行う static void ExecDP(Dictionary[] pDPDictArr, long pWeightLimit) { long UB = pDPDictArr.GetUpperBound(0); var AnswerIndList = new List(); long CurrInd = 0; long CurrWeightLimit = pWeightLimit; while (true) { if (CurrInd > UB) break; var CurrDict = pDPDictArr[CurrInd]; var Tmp1 = CurrDict.Where(pX => pX.Key <= CurrWeightLimit); var Tmp2 = Tmp1.OrderByDescending(pX => pX.Value.Score); var Tmp3 = Tmp2.ThenByDescending(pX => pX.Value.LastItemInd); if (Tmp3.Any() == false) break; JyoutaiDef CurrAnswer = Tmp3.First().Value; AnswerIndList.Add(CurrAnswer.LastItemInd); CurrWeightLimit -= mItemInfoArr[CurrAnswer.LastItemInd].Weight; CurrInd = CurrAnswer.LastItemInd + 1; } Console.WriteLine(AnswerIndList.Count); for (int I = 0; I <= AnswerIndList.Count - 1; I++) { // 1オリジンに変更 AnswerIndList[I]++; } Console.WriteLine(LongEnumJoin(" ", AnswerIndList)); } struct JyoutaiDef { internal long Score; internal long LastItemInd; } // セパレータとLong型の列挙を引数として、結合したstringを返す static string LongEnumJoin(string pSeparater, IEnumerable pEnum) { string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString()); return string.Join(pSeparater, StrArr); } }