結果

問題 No.489 株に挑戦
ユーザー aimyaimy
提出日時 2017-06-01 13:14:59
言語 Haskell
(9.8.2)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 2 ms
5,376 KB
testcase_09 WA -
testcase_10 AC 2 ms
5,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 42 ms
12,416 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 338 ms
43,520 KB
testcase_27 AC 414 ms
55,680 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 WA -
testcase_31 AC 360 ms
54,016 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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