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() { //var sw = System.Diagnostics.Stopwatch.StartNew(); 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); // {スコア , 最後に選択したInd} [重さ]なインラインDP表 var DPDict = new Dictionary(); for (long I = UB; 0 <= I; I--) { var CurrUpdateInfoList = new List(); Action UpdateAct = (pNewScore, pWeightSum) => { if (pWeightSum > mWeightLimit) return; bool IsOK = false; if (DPDict.ContainsKey(pWeightSum)) { if (DPDict[pWeightSum].Score < pNewScore) { IsOK = true; } //else if (DPDict[pWeightSum].Score == pNewScore) { // if (DPDict[pWeightSum].LastItemInd < I) { // IsOK = true; // } //} } else { IsOK = true; } if (IsOK) { UpdateInfoDef CurrUpdateInfo; CurrUpdateInfo.Weight = pWeightSum; CurrUpdateInfo.Score = pNewScore; CurrUpdateInfo.LastItemInd = I; CurrUpdateInfoList.Add(CurrUpdateInfo); } }; foreach (var EachPair in DPDict) { UpdateAct(EachPair.Value.Score + mItemInfoArr[I].Score, EachPair.Key + mItemInfoArr[I].Weight); } UpdateAct(mItemInfoArr[I].Score, mItemInfoArr[I].Weight); foreach (UpdateInfoDef EachUpdateInfo in CurrUpdateInfoList) { DPDict[EachUpdateInfo.Weight] = new JyoutaiDef(); DPDict[EachUpdateInfo.Weight].Score = EachUpdateInfo.Score; DPDict[EachUpdateInfo.Weight].LastItemInd = EachUpdateInfo.LastItemInd; } } foreach (var EachPair in DPDict) { UpdateInfoDef CurrUpdateInfo; CurrUpdateInfo.Weight = EachPair.Key; CurrUpdateInfo.Score = EachPair.Value.Score; CurrUpdateInfo.LastItemInd = EachPair.Value.LastItemInd; mUpdateInfoList.Add(CurrUpdateInfo); } //foreach (UpdateInfoDef EachUpdateInfo in mUpdateInfoList) { // Console.WriteLine("Weight={0},Score={1},LastItemInd={2}", // EachUpdateInfo.Weight, EachUpdateInfo.Score, EachUpdateInfo.LastItemInd); //} ExecDP(); //Console.WriteLine(sw.Elapsed); } class JyoutaiDef { internal long Score; internal long LastItemInd; } // DPの更新情報 struct UpdateInfoDef { internal long Weight; internal long Score; internal long LastItemInd; } static List mUpdateInfoList = new List(); // DP復元を行う static void ExecDP() { var AnswerIndList = new List(); long CurrInd = 0; long CurrWeightLimit = mWeightLimit; while (true) { // RemoveAllで不要データの削除 mUpdateInfoList.RemoveAll(pX => pX.Weight > CurrWeightLimit || pX.LastItemInd < CurrInd); // 定数倍改善でソートを定義できる構造体にする余地あり var Tmp1 = mUpdateInfoList.OrderByDescending(pX => pX.Score); var Tmp2 = Tmp1.ThenByDescending(pX => pX.LastItemInd); if (Tmp2.Any() == false) break; UpdateInfoDef CurrAnswer = Tmp2.First(); AnswerIndList.Add(CurrAnswer.LastItemInd); CurrWeightLimit -= mItemInfoArr[CurrAnswer.LastItemInd].Weight; CurrInd = CurrAnswer.LastItemInd + 1; //Console.WriteLine("CurrWeightLimit={0},", CurrWeightLimit); //Console.WriteLine("CurrInd={0},", CurrInd); } Console.WriteLine(AnswerIndList.Count); for (int I = 0; I <= AnswerIndList.Count - 1; I++) { // 1オリジンに変更 AnswerIndList[I]++; } Console.WriteLine(LongEnumJoin(" ", AnswerIndList)); } // セパレータとLong型の列挙を引数として、結合したstringを返す static string LongEnumJoin(string pSeparater, IEnumerable pEnum) { string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString()); return string.Join(pSeparater, StrArr); } }