#153192 (C#(csc)) No.489 株に挑戦

• 問題: No.489 株に挑戦
• ユーザー: kuuso1
• 提出日時: 2017-02-26 15:12:15
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 107 ms / 1,000 ms
• コード長: 3,242 bytes
• コンパイル時間: 2,720 ms
• コンパイル使用メモリ: 108,416 KB
• 実行使用メモリ: 22,656 KB
• 最終ジャッジ日時: 2024-07-19 23:33:17
• 合計ジャッジ時間: 6,165 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	81 ms; 21,632 KB
testcase_01	AC	60 ms; 19,840 KB
testcase_02	AC	23 ms; 18,176 KB
testcase_03	AC	23 ms; 17,920 KB
testcase_04	AC	21 ms; 17,920 KB
testcase_05	AC	22 ms; 17,664 KB
testcase_06	AC	22 ms; 18,048 KB
testcase_07	AC	23 ms; 17,792 KB
testcase_08	AC	22 ms; 17,792 KB
testcase_09	AC	23 ms; 18,048 KB
testcase_10	AC	20 ms; 18,048 KB
testcase_11	AC	23 ms; 17,664 KB
testcase_12	AC	25 ms; 17,792 KB
testcase_13	AC	24 ms; 18,048 KB
testcase_14	AC	24 ms; 18,048 KB
testcase_15	AC	26 ms; 18,176 KB
testcase_16	AC	95 ms; 21,376 KB
testcase_17	AC	32 ms; 18,380 KB
testcase_18	AC	60 ms; 19,580 KB
testcase_19	AC	54 ms; 19,144 KB
testcase_20	AC	96 ms; 22,272 KB
testcase_21	AC	39 ms; 18,728 KB
testcase_22	AC	28 ms; 18,400 KB
testcase_23	AC	65 ms; 20,224 KB
testcase_24	AC	107 ms; 22,528 KB
testcase_25	AC	22 ms; 17,792 KB
testcase_26	AC	93 ms; 21,632 KB
testcase_27	AC	100 ms; 21,888 KB
testcase_28	AC	23 ms; 17,792 KB
testcase_29	AC	22 ms; 18,176 KB
testcase_30	AC	91 ms; 22,656 KB
testcase_31	AC	92 ms; 21,760 KB
testcase_32	AC	64 ms; 20,096 KB
testcase_33	AC	103 ms; 22,528 KB
testcase_34	AC	90 ms; 22,016 KB
testcase_35	AC	50 ms; 19,348 KB
testcase_36	AC	33 ms; 18,672 KB
testcase_37	AC	58 ms; 20,088 KB

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		var ST = new SegTree(N);
		//ST.Init(A);
		for(int i=0;i<N;i++){
			ST.Update(i,A[i]);
		}
//ST.Dump();		
		int max = 0;
		int buy = -1;
		for(int i=0;i<N;i++){
			int mm = ST.QueryMax(i,i+D+1);
			int inc = mm - A[i];
			if(inc > max){
				max = inc;
				buy = i;
			}
		}
		
		int sell = 0;
		if(max != 0){
			for(int i=buy;i<Math.Min(buy+D+1,N);i++){
				if(A[i] - A[buy] == max){
					sell = i;
					break;
				}
			}
		}
		
		Console.WriteLine(K * max);
		if(max != 0){
			Console.WriteLine("{0} {1}",buy,sell);
		}
	}
	int N,D;
	long K;
	int[] A;
	public Sol(){
		var d = ria();
		N = d[0]; D = d[1]; K = d[2];
		A = new int[N];
		for(int i=0;i<N;i++) A[i] = ri();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}



class SegTree{
	//segment Tree 
	// 0-origin
	public int[] Data;	//実体
	public int Inf;	//初期化用のlargeNumber
	public int N;		//size 
	public int n;		//size (2の冪)
	
	//コンストラクタ
	public SegTree(int n_){
		N=n_;Inf=- (int)2e9;
		n=1;
		while(n<n_)n*=2;
		Data=new int[2*n-1];
		for(int i=0;i<2*n-1;i++)Data[i]=Inf;
	}
	
	//k-番目の値をaに変更(ヒープ：各ノードは両手のMinを値に持つ）
	//	   0
	//	 1   2
	//	3 4 5 6
	public void Update(int k,int a){
		k+=n-1;	//上にはn-1個乗る
		Data[k]=a;
		while(k>0){
			k=(k-1)/2;
			Data[k]=Math.Max(Data[k*2+1],Data[k*2+2]);
		}
	}
	
	public int QueryMax (int a, int b){
		return Query(a, b, 0, 0, n);
	}
	
	//RMQ;
	//	[a,b) のMinを返す
	//	後ろ3つの引数は	k,l,r：ヒープのk-ノードが範囲 [l,r) に対応していることを示す
	//	外から呼ぶ時は Query(a,b,0,0,n) の形で呼ぶ
	public int Query(int a,int b,int k,int l,int r){
		// [a,b) ∩ [l,r) =φ　⇒Infを返す
		if(r<=a || b<=l) return Inf;
		// [a,b) ⊃ [l,r) ⇒Data[k]を返す 
		if(a<=l && r<=b)return Data[k];
		// さもなくば、両手のうち小さい方を返す
		int vl=Query(a,b,k*2+1,l,(l+r)/2);
		int vr=Query(a,b,k*2+2,(l+r)/2,r);
		return Math.Max(vl,vr);
	}
	
	public void Init(int[] A){
		for(int i=0;i<A.Length;i++){
			Data[i + n - 1] = A[i];
		}
		for(int j=n-2;j>=0;j--){
			Data[j] = Math.Max(Data[2*j+1], Data[2*j+2]);
		}	
	}
	
	
	public void Dump(){
		Console.WriteLine();
		int h=0;
		int cnt=0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ",Data[i] == Inf ? "X" : Data[i].ToString());
			cnt++;
			if(cnt==1<<h){
				cnt=0;
				h++;
				Console.WriteLine();
			}
		}
	}
	
}