結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2024-10-10 20:48:23 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 496 ms / 1,000 ms |
コード長 | 6,662 bytes |
コンパイル時間 | 8,007 ms |
コンパイル使用メモリ | 167,172 KB |
実行使用メモリ | 230,896 KB |
最終ジャッジ日時 | 2024-10-10 20:48:42 |
合計ジャッジ時間 | 18,554 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (96 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using System.Collections.Generic;using System.Linq;class Program{static string InputPattern = "InputX";static List<string> GetInputList(){var WillReturn = new List<string>();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<string> InputList = GetInputList();int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();int N = wkArr[0];int D = wkArr[1];int K = wkArr[2];int[] XArr = InputList.Skip(1).Take(N).Select(pX => int.Parse(pX)).ToArray();int UB = XArr.GetUpperBound(0);var InsSparseTable = new SparseTable<int>(XArr, false);// IndのList[値]なDictvar IndListDict = new Dictionary<int, List<int>>();for (int I = 0; I <= UB; I++) {if (IndListDict.ContainsKey(XArr[I]) == false) {IndListDict[XArr[I]] = new List<int>();}IndListDict[XArr[I]].Add(I);}var AnswerKouho = new List<ProfitInfoDef>();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 = (long)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<int> 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<Type>{private Type[] mInitArr;private int UB_0;private int UB_1;// 最小値か最大値[開始Ind,2の指数]なArrprivate Type[,] mMinOrMaxArr;// Log2の値[2べきな値] なDictstatic Dictionary<int, int> mLogDict = new Dictionary<int, int>();// 最小値を取得するか?private bool mIsMin = false;// コンストラクタinternal SparseTable(IEnumerable<Type> 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<Type>();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<Type>();KouhoList.Add(mMinOrMaxArr[pL, Sisuu]);KouhoList.Add(mMinOrMaxArr[pR - Beki2 + 1, Sisuu]);if (mIsMin) {return KouhoList.Min();}return KouhoList.Max();}}#endregion