Submission #37463913

---

Source Code Expand

#!/usr/bin/env stack
{- stack script --resolver lts-16.11
--package array --package bytestring --package containers
--package vector --package vector-algorithms --package primitive --package transformers
-}

{- ORMOLU_DISABLE -}
{-# LANGUAGE BangPatterns, BlockArguments, LambdaCase, MultiWayIf, PatternGuards, TupleSections #-}
{-# LANGUAGE NumDecimals, NumericUnderscores #-}
{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, ScopedTypeVariables, TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
{- ORMOLU_ENABLE -}

-- {{{ Imports

module Main (main) where

import Control.Monad
import Data.Char
import Data.List

{- ORMOLU_DISABLE -}

-- array
import Data.Array.IArray
import Data.Array.IO
import Data.Array.MArray
import Data.Array.ST
import Data.Array.Unsafe

import qualified Data.Array as A
import qualified Data.Array.Unboxed as AU

-- bytestring: https://www.stackage.org/lts-16.11/package/bytestring-0.10.10.0
import qualified Data.ByteString.Char8 as BS

-- vector: https://www.stackage.org/lts-16.11/package/vector-0.12.1.2
import qualified Data.Vector.Unboxed as VU

{- ORMOLU_ENABLE -}

getLineIntList :: IO [Int]
getLineIntList = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

main :: IO ()
main = do
  [nItems, wLimit] <- getLineIntList
  wvs <- VU.replicateM nItems $ (\[a, b] -> (a, b)) <$> getLineIntList

  let dp = runSTArray $ do
      let rng = ((0, 0), (nItems, wLimit))
      arr <- newArray rng (0 :: Int)

      forM_ (range rng) $ \(i, w) -> do
        e <- if w == 0 || i == 0
          then return 0
          else do
            let wv = wvs VU.! (i - 1)
            v1 <- readArray arr (i - 1, w)
            v2 <- if w - fst wv >= 0 then (snd wv +) <$> readArray arr (i - 1, w - fst wv) else return 0
            return $ max v1 v2

        writeArray arr (i, w) e

      return arr

  print $ maximum [dp ! (nItems, w) | w <- [0..wLimit]]

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result