結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2023-06-13 01:13:51 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,432 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 17,024 KB |
最終ジャッジ日時 | 2024-06-12 00:19:51 |
合計ジャッジ時間 | 16,840 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 TLE * 4 |
ソースコード
import sysinput = sys.stdin.readlineN,D,K=map(int,input().split())A=[int(input()) for i in range(N)]# Segment tree(1-indexed,再帰を使わないもの。非可換の場合にも対応)def seg_function(x,y): # Segment treeで扱うfunctionreturn max(x,y)seg_el=1<<(N.bit_length()) # Segment treeの台の要素数SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化for i in range(N): # Aを対応する箇所へupdateSEG[i+seg_el]=A[i]for i in range(seg_el-1,0,-1): # 親の部分もupdateSEG[i]=seg_function(SEG[i*2],SEG[i*2+1])def update(n,x,seg_el): # A[n]をxへ更新i=n+seg_elSEG[i]=xi>>=1 # 子ノードへwhile i!=0:SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])i>>=1def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べるL=l+seg_elR=r+seg_elANS1=0ANS2=0while L<R:if L & 1:ANS1=seg_function(ANS1, SEG[L])L+=1if R & 1:R-=1ANS2=seg_function(SEG[R], ANS2)L>>=1R>>=1return seg_function(ANS1, ANS2)ANS=-1<<60for i in range(N):x=getvalues(i+1,min(N,i+D+1))if ANS<x-A[i]:ANS=x-A[i]ind=iif ANS<=0:print(0)exit()for j in range(ind,ind+D+1):if A[j]-A[ind]==ANS:print(ANS*K)print(ind,j)break