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 Value; 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.Value = ValueArr[I]; WillAdd.Weight = WeightArr[I]; ItemInfoList.Add(WillAdd); } // 状態[重さ合計]なインラインDP表 JyoutaiDef[] DPArr = new JyoutaiDef[WeightLimit + 1]; var FirstJyoutai = new JyoutaiDef(); FirstJyoutai.IndList = ""; FirstJyoutai.Score = 0; DPArr[0] = FirstJyoutai; for (int I = 0; I <= ItemInfoList.Count - 1; I++) { for (long J = WeightLimit; 0 <= J; J--) { if (DPArr[J] == null) continue; long NewJ = J + ItemInfoList[I].Weight; if (NewJ > WeightLimit) continue; long NewScore = DPArr[J].Score + ItemInfoList[I].Value; string NewIndList = DPArr[J].IndList + I.ToString().PadLeft(4, '0'); if (DPArr[NewJ] != null) { if (DPArr[NewJ].Score > NewScore) { continue; } if (DPArr[NewJ].Score == NewScore) { int CompareResult = DPArr[NewJ].IndList.CompareTo(NewIndList); if (CompareResult >= 0) { continue; } } } var NewJyoutai = new JyoutaiDef(); NewJyoutai.IndList = NewIndList; NewJyoutai.Score = NewScore; DPArr[NewJ] = NewJyoutai; } } var Query = DPArr.Where(pX => pX != null).OrderByDescending(pX => pX.Score).Select(pX => pX.IndList); string AnswerIndList = Query.First(); var AnswerList = new List(); for (int I = 0; I <= AnswerIndList.Length - 1; I += 4) { long CurrVal = long.Parse(AnswerIndList.Substring(I, 4)); AnswerList.Add(CurrVal + 1); } Console.WriteLine(AnswerList.Count); Console.WriteLine(LongEnumJoin(" ", AnswerList)); } class JyoutaiDef { internal string IndList; internal long Score; } // セパレータとLong型の列挙を引数として、結合したstringを返す static string LongEnumJoin(string pSeparater, IEnumerable pEnum) { string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString()); return string.Join(pSeparater, StrArr); } }