Submission #5209599

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Char
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM
import qualified Data.ByteString.Char8 as BS
main = do
  [n,!k] <- map (read . BS.unpack) . BS.words <$> BS.getLine
  -- 2 <= n <= 10^5, 1 <= k <= 100
  h <- V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  -- 1 <= hi <= 10^4
  let dp = V.constructN n $ \dp ->
        if V.null dp
        then 0
        else let !i = V.length dp
                 !h_i = h V.! i
             in V.minimum $ V.map (\(dp_j, h_j) -> dp_j + abs (h_i - h_j)) $ V.drop (i-k) $ V.zip dp h
  print (V.last dp :: Int)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Char
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM
import qualified Data.ByteString.Char8 as BS

main = do
  [n,!k] <- map (read . BS.unpack) . BS.words <$> BS.getLine
  -- 2 <= n <= 10^5, 1 <= k <= 100
  h <- V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  -- 1 <= hi <= 10^4
  let dp = V.constructN n $ \dp ->
        if V.null dp
        then 0
        else let !i = V.length dp
                 !h_i = h V.! i
             in V.minimum $ V.map (\(dp_j, h_j) -> dp_j + abs (h_i - h_j)) $ V.drop (i-k) $ V.zip dp h
  print (V.last dp :: Int)

Submission Info

Judge Result