結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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();
			}
		}
	}
	
}
0