using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/489 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("7 2 1000"); WillReturn.Add("1"); WillReturn.Add("3"); WillReturn.Add("5"); WillReturn.Add("1"); WillReturn.Add("4"); WillReturn.Add("4"); WillReturn.Add("7"); //4000 //0 2 } else if (InputPattern == "Input2") { WillReturn.Add("5 4 100"); WillReturn.Add("1"); WillReturn.Add("2"); WillReturn.Add("1"); WillReturn.Add("2"); WillReturn.Add("1"); //100 //0 1 } else if (InputPattern == "Input3") { WillReturn.Add("5 1 100"); WillReturn.Add("5"); WillReturn.Add("4"); WillReturn.Add("3"); WillReturn.Add("3"); WillReturn.Add("1"); //0 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct ProfitInfoDef { internal int BuyInd; internal int SellInd; internal long Profit; } static void Main() { List InputList = GetInputList(); int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray(); int D = wkArr[1]; int K = wkArr[2]; int[] XArr = InputList.Skip(1).Select(pX => int.Parse(pX)).ToArray(); int UB = XArr.GetUpperBound(0); var InsSparseTable = new SparseTable(XArr, false); // IndのList[値]なDict var IndListDict = new Dictionary>(); for (int I = 0; I <= UB; I++) { if (IndListDict.ContainsKey(XArr[I]) == false) { IndListDict[XArr[I]] = new List(); } IndListDict[XArr[I]].Add(I); } var AnswerKouho = new List(); for (int I = 0; I <= UB; I++) { int RangeSta = I; int RangeEnd = I + D; RangeEnd = Math.Min(UB, RangeEnd); int MaxVal = InsSparseTable.Query(RangeSta, RangeEnd); ProfitInfoDef WillAdd; WillAdd.BuyInd = I; int ResultNibunhou = ExecNibunhou_LowerBound(I, IndListDict[MaxVal]); WillAdd.SellInd = IndListDict[MaxVal][ResultNibunhou]; WillAdd.Profit = K * (XArr[WillAdd.SellInd] - XArr[WillAdd.BuyInd]); AnswerKouho.Add(WillAdd); } if (AnswerKouho.Exists(pX => pX.Profit > 0)) { ProfitInfoDef AnswerItem = AnswerKouho.OrderByDescending(pX => pX.Profit).First(); Console.WriteLine(AnswerItem.Profit); Console.WriteLine("{0} {1}", AnswerItem.BuyInd, AnswerItem.SellInd); } else { Console.WriteLine(0); } } // 二分法で、Val以上で最小の値を持つ、添字を返す static int ExecNibunhou_LowerBound(int pVal, List pList) { // 最後の要素がVal未満の特殊ケース if (pVal > pList.Last()) { return -1; } // 最初の要素がVal以上の特殊ケース if (pVal <= pList[0]) { return 0; } int L = 0; int R = pList.Count - 1; while (L + 1 < R) { int Mid = (L + R) / 2; if (pList[Mid] >= pVal) { R = Mid; } else { L = Mid; } } return R; } } #region SparseTable // スパーステーブル internal class SparseTable { private Type[] mInitArr; private int UB_0; private int UB_1; // 最小値か最大値[開始Ind,2の指数]なArr private Type[,] mMinOrMaxArr; // Log2の値[2べきな値] なDict static Dictionary mLogDict = new Dictionary(); // 最小値を取得するか? private bool mIsMin = false; // コンストラクタ internal SparseTable(IEnumerable pInitEnum, bool pIsMin) { mIsMin = pIsMin; mInitArr = pInitEnum.ToArray(); UB_0 = mInitArr.GetUpperBound(0); int Sisuu = 0; int Beki2 = 1; while (true) { mLogDict[Beki2] = Sisuu; if (Beki2 > mInitArr.Length) { break; } Beki2 *= 2; Sisuu++; } UB_1 = Sisuu; mMinOrMaxArr = new Type[UB_0 + 1, UB_1 + 1]; // 長さ1の分を初期化 for (int I = 0; I <= UB_0; I++) { mMinOrMaxArr[I, 0] = mInitArr[I]; } for (int LoopLength = 2; LoopLength < int.MaxValue; LoopLength *= 2) { bool WillBreak = true; int HalfRange = LoopLength / 2; for (int I = 0; I <= UB_0; I++) { int StaInd1 = I; int EndInd1 = I + HalfRange - 1; int StaInd2 = EndInd1 + 1; int EndInd2 = StaInd2 + HalfRange - 1; if (EndInd2 > UB_0) break; var KouhoList = new List(); KouhoList.Add(mMinOrMaxArr[I, mLogDict[HalfRange]]); KouhoList.Add(mMinOrMaxArr[StaInd2, mLogDict[HalfRange]]); if (mIsMin) { mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Min(); } else { mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Max(); } WillBreak = false; } if (WillBreak) break; } } // 閉区間 [L,R]の最小値または最大値を求める internal Type Query(int pL, int pR) { // 区間を内包する2べきを返す int Beki2 = 1; int Sisuu = 0; while (true) { int LeftRangeMax = pL + Beki2 - 1; int RightRangeMin = pR - Beki2 + 1; if (LeftRangeMax + 1 >= RightRangeMin) { break; } Beki2 *= 2; Sisuu++; } var KouhoList = new List(); KouhoList.Add(mMinOrMaxArr[pL, Sisuu]); KouhoList.Add(mMinOrMaxArr[pR - Beki2 + 1, Sisuu]); if (mIsMin) { return KouhoList.Min(); } return KouhoList.Max(); } } #endregion