結果

問題 No.489 株に挑戦
ユーザー aketijyuuzou
提出日時 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/

ソースコード

diff #
プレゼンテーションモードにする

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);
// IndList[]Dict
var 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]Arr
private Type[,] mMinOrMaxArr;
// Log2[2] Dict
static 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0