結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-27 22:33:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 948 ms / 1,000 ms |
コード長 | 1,105 bytes |
コンパイル時間 | 388 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 113,052 KB |
最終ジャッジ日時 | 2024-06-11 19:59:01 |
合計ジャッジ時間 | 16,376 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
INF=-1000000007N,D,K = map(int,input().split())x = [int(input()) for i in range(N)]seg = []size = 1 << 17seg=[[INF,INF] for i in range(size*2)]def seg_update(i,X):tmp=[X,i]i = size+i-1seg[i]=tmpwhile i > 0:i = (i-1)>>1i1,i2=i*2+1,i*2+2if seg[i1][0] < seg[i2][0]:seg[i] = seg[i2]elif seg[i1][0] > seg[i2][0]:seg[i] = seg[i1]else:if seg[i1][1] < seg[i2][1]:seg[i] = seg[i1]else:seg[i] = seg[i2]def seg_query(a,b,k,l,r):if r <= a or b <= l:return [INF,INF]if a <= l and r <= b:return seg[k]left=seg_query(a,b,2*k+1,l,(l+r)>>1)right=seg_query(a,b,2*k+2,(l+r)>>1,r)if left[0] == INF:return rightif right[0] == INF:return leftif left[0] < right[0]:return rightelif left[0] > right[0]:return leftelse:if left[1] < right[1]:return leftelse:return rightfor i in range(N):seg_update(i,x[i])ans=INFpair=[INF,INF]for i in range(N-1):ret=seg_query(i+1,min(N,i+D+1),0,0,size+1)if ans < ret[0]-x[i]:ans=ret[0]-x[i]pair=[i,ret[1]]if ans <= 0:print(0)else:print(ans*K)print(pair[0],pair[1])