結果

問題 No.489 株に挑戦
ユーザー aimy
提出日時 2017-06-01 13:14:59
言語 Haskell
(9.10.1)
結果
WA  
実行時間 -
コード長 1,188 bytes
コンパイル時間 6,279 ms
コンパイル使用メモリ 192,000 KB
実行使用メモリ 59,648 KB
最終ジャッジ日時 2024-09-21 21:38:52
合計ジャッジ時間 13,167 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

main = do
 [n,d,k] <- map read . words <$> getLine
 xs <- map read . words <$> getContents
 let (pmax, jk) = kabu n d k xs
 print (k * pmax)
 maybe (return ()) (\(j,k) -> putStrLn (show j ++ " " ++ show k)) jk

kabu n d k xs = foldl (update n seg) (0,Nothing) [(j,j+d) | j<-[0..n-d-1]]
 where seg = fromList n (zipWith (\i x -> ((i,i),(x,x))) [0..] xs)

update n seg (pmax,jk) (j,k)
 | profit p > pmax = (profit p, Just i)
 | otherwise = (pmax, jk)
 where 
  (i,p) = query n seg j k
  profit (x,y) = y - x


data SegTree a = Leaf a | Node a (SegTree a) (SegTree a) deriving (Eq, Ord, Show)

minmax ((i,j),(a,b)) ((k,l),(c,d))
 | max a b < y = ((i,l),(x,y))
 | otherwise = ((i,j),(x,y))
 where
  x = min a b
  y = max c d

val (Leaf v) = v
val (Node v _ _) = v

fromList 1 [x] = Leaf x
fromList n xs  = Node (minmax (val left) (val right)) left right
 where
  n' = div n 2
  (xs1,xs2) = splitAt n' xs
  left = fromList n' xs1
  right = fromList (n-n') xs2

query 1 (Leaf v) 0 0 = v
query n (Node v l r) i j
 | (i,j) == (0,n-1) = v
 | j < n' = query n' l i j
 | i >= n' = query (n-n') r (i-n') (j-n')
 | otherwise = minmax (query n' l i (n'-1)) (query (n-n') r 0 (j-n'))
 where n' = div n 2
0