結果
問題 | No.489 株に挑戦 |
ユーザー | kuuso1 |
提出日時 | 2017-02-26 14:55:14 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,126 bytes |
コンパイル時間 | 2,898 ms |
コンパイル使用メモリ | 111,152 KB |
実行使用メモリ | 27,768 KB |
最終ジャッジ日時 | 2023-09-02 09:55:06 |
合計ジャッジ時間 | 7,051 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 60 ms
20,804 KB |
testcase_03 | AC | 60 ms
22,836 KB |
testcase_04 | AC | 57 ms
22,744 KB |
testcase_05 | AC | 61 ms
20,876 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 61 ms
21,008 KB |
testcase_09 | AC | 61 ms
20,828 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 61 ms
20,956 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 107 ms
23,736 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 113 ms
23,572 KB |
testcase_21 | AC | 73 ms
20,828 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 56 ms
20,768 KB |
testcase_26 | AC | 129 ms
23,680 KB |
testcase_27 | WA | - |
testcase_28 | AC | 61 ms
20,740 KB |
testcase_29 | AC | 56 ms
20,768 KB |
testcase_30 | AC | 132 ms
23,676 KB |
testcase_31 | AC | 134 ms
23,564 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | AC | 70 ms
20,924 KB |
testcase_37 | AC | 95 ms
23,024 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); int max = 0; int buy = -1; for(int i=0;i<N;i++){ int inc = ST.QueryMax(i,D+1) - 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]); cnt++; if(cnt==1<<h){ cnt=0; h++; Console.WriteLine(); } } } }