using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("5 2"); WillReturn.Add("10 20 30 40 50"); //80 } else if (InputPattern == "Input2") { WillReturn.Add("4 3"); WillReturn.Add("-10 -20 100 100"); //Impossible } else if (InputPattern == "Input3") { WillReturn.Add("4 2"); WillReturn.Add("-10 -20 100 100"); //90 } 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(); } static void Main() { List InputList = GetInputList(); long[] wkArr = GetSplitArr(InputList[0]); long K = wkArr[1]; long[] AArr = GetSplitArr(InputList[1]); // 最大スコア[消した数 , 次に消せるか]なDP表 long?[,] PrevDP = new long?[K + 1, 2]; PrevDP[0, 1] = 0; foreach (long EachA in AArr) { long?[,] CurrDP = new long?[K + 1, 2]; for (long I = 0; I <= K; I++) { for (long J = 0; J <= 1; J++) { if (PrevDP[I, J].HasValue == false) continue; Action UpdateAct = (pNewI, pNewJ, pNewVal) => { if (pNewI > K) return; if (CurrDP[pNewI, pNewJ].HasValue) { if (CurrDP[pNewI, pNewJ].Value >= pNewVal) { return; } } CurrDP[pNewI, pNewJ] = pNewVal; }; // 消す遷移 if (J == 1) { UpdateAct(I + 1, 0, PrevDP[I, J].Value + EachA); } // 消さない遷移 UpdateAct(I, 1, PrevDP[I, J].Value); } } PrevDP = CurrDP; } var AnswerList = new List(); for (long J = 0; J <= 1; J++) { if (PrevDP[K, J].HasValue) { AnswerList.Add(PrevDP[K, J].Value); } } if (AnswerList.Count == 0) { Console.WriteLine("Impossible"); } else { Console.WriteLine(AnswerList.Max()); } } }