提出 #47201536

---

ソースコード 拡げる

import Control.DeepSeq
import Data.ByteString.Char8 qualified as BS
import Data.Bool (bool)
import Data.Char (isSpace)
import Data.IntMap.Strict qualified as IM
import Data.Maybe
import Data.Vector qualified as V
import Data.Vector.Unboxed qualified as U

ints2 :: BS.ByteString -> ((Int, Int), BS.ByteString)
ints2 !bs0 =
  let (!a1, !bs1) = fromJust $ BS.readInt (BS.dropWhile isSpace bs0)
      (!a2, !bs2) = fromJust $ BS.readInt (BS.dropWhile isSpace bs1)
   in ((a1, a2), bs2)

readInput :: IO ((Int, Int), U.Vector (Int, Int))
readInput = do
  !bs <- BS.getContents
  let ((!n, !maxW), !bs') = ints2 bs
  let vws = U.unfoldrExactN n ints2 bs'
  return ((n, maxW), vws)

denseU :: Int -> U.Vector (Int, Int) -> Int
denseU maxW = U.maximum . U.foldl' step s0
  where
    s0 = U.generate (maxW + 1) $ bool minBound 0 . (== 0)
    step sofar (!dw, !dv) = U.imap f sofar
      where
        f :: Int -> Int -> Int
        f w0 v0 = max v0 $ maybe 0 (dv +) (sofar U.!? (w0 - dw))

denseV :: Int -> U.Vector (Int, Int) -> Int
denseV maxW = V.maximum . U.foldl' step s0
  where
    s0 = V.generate (maxW + 1) $ bool minBound 0 . (== 0)
    step sofar (!dw, !dv) = V.imap f sofar
      where
        f :: Int -> Int -> Int
        f w0 v0 = max v0 $ maybe 0 (dv +) (sofar V.!? (w0 - dw))

sparseList :: Int -> U.Vector (Int, Int) -> Int
sparseList maxW = maximum . map snd . U.foldl' step s0
  where
    s0 = [(0, 0)] :: [(Int, Int)]
    step wvs (!dw, !dv) =
      merge wvs $ filter ((<= maxW) . fst) $ map (\(!w, !v) -> (w + dw, v + dv)) wvs

    merge :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
    merge xs [] = xs
    merge [] xs = xs
    merge xxs@(!x : xs) yys@(!y : ys) = case compare (fst x) (fst y) of
      LT -> x : merge xs yys
      GT -> y : merge xxs ys
      EQ -> (fst x, max (snd x) (snd y)) : merge xs ys

sparseListNotForced :: Int -> U.Vector (Int, Int) -> Int
sparseListNotForced maxW = maximum . map snd . U.foldl' step s0
  where
    s0 = [(0, 0)] :: [(Int, Int)]
    step wvs (!dw, !dv) =
      {- force . -} merge wvs $ filter ((<= maxW) . fst) $ map (\(!w, !v) -> (w + dw, v + dv)) wvs

    merge :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
    merge xs [] = xs
    merge [] xs = xs
    merge xxs@(!x : xs) yys@(!y : ys) = case compare (fst x) (fst y) of
      LT -> x : merge xs yys
      GT -> y : merge xxs ys
      EQ -> (fst x, max (snd x) (snd y)) : merge xs ys

sparseIM :: Int -> U.Vector (Int, Int) -> Int
sparseIM maxW = maximum . U.foldl' step s0
  where
    s0 = IM.singleton (0 :: Int) (0 :: Int)
    step wvs (!dw, !dv) =
      IM.unionWith max wvs $ IM.fromList . filter ((<= maxW) . fst) . map (\(!w, !v) -> (w + dw, v + dv)) $ IM.assocs wvs

sparseU :: Int -> U.Vector (Int, Int) -> Int
sparseU maxW = U.maximum . U.map snd . U.foldl' step s0
  where
    s0 = U.singleton (0 :: Int, 0 :: Int)
    step wvs (!dw, !dv) =
      U.unfoldr merge . (,) wvs $ U.filter ((<= maxW) . fst) $ U.map (\(!w, !v) -> (w + dw, v + dv)) wvs

    merge :: (U.Vector (Int, Int), U.Vector (Int, Int)) -> Maybe ((Int, Int), (U.Vector (Int, Int), U.Vector (Int, Int)))
    merge (!xs, !ys) = case (U.uncons xs, U.uncons ys) of
      (Nothing, Nothing) -> Nothing
      (Just (!x, !xs'), Nothing) -> Just (x, (xs', U.empty))
      (Nothing, Just (!y, !ys')) -> Just (y, (U.empty, ys'))
      (Just (!x, !xs'), Just (!y, !ys')) -> case compare (fst x) (fst y) of
        LT -> Just (x, (xs', ys))
        GT -> Just (y, (xs, ys'))
        EQ -> Just ((fst x, max (snd x) (snd y)), (xs', ys'))

sparseMonoList :: Int -> U.Vector (Int, Int) -> Int
sparseMonoList maxW = maximum . map snd . U.foldl' step s0
  where
    s0 = [(0, 0)] :: [(Int, Int)]
    step wvs (!dw, !dv) =
      merge (-1 :: Int) wvs $ filter ((<= maxW) . fst) $ map (\(!w, !v) -> (w + dw, v + dv)) wvs

    merge :: Int -> [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
    merge _ xs [] = xs
    merge _ [] ys = ys
    merge maxV xxs@(x : xs) yys@(y : ys)
      | snd x <= maxV = merge maxV xs yys
      | snd y <= maxV = merge maxV xxs ys
      | otherwise = case compare (fst x) (fst y) of
          LT -> x : merge (max maxV (snd x)) xs yys
          GT -> y : merge (max maxV (snd y)) xxs ys
          EQ ->
            if maxV' == maxV
              then merge maxV' xs ys
              else (fst x, maxV') : merge maxV' xs ys
            where
              !maxV' = max (snd x) (snd y) `max` maxV

sparseMonoU :: Int -> U.Vector (Int, Int) -> Int
sparseMonoU maxW = U.maximum . U.map snd . U.foldl' step s0
  where
    s0 = U.singleton (0 :: Int, 0 :: Int)
    step wvs (!dw, !dv) =
      U.unfoldr merge . (,,) (-1 :: Int) wvs $ U.filter ((<= maxW) . fst) $ U.map (\(!w, !v) -> (w + dw, v + dv)) wvs

    merge :: (Int, U.Vector (Int, Int), U.Vector (Int, Int)) -> Maybe ((Int, Int), (Int, U.Vector (Int, Int), U.Vector (Int, Int)))
    merge (!maxV, !xs, !ys) = case (U.uncons xs, U.uncons ys) of
      (Nothing, Nothing) -> Nothing
      (Just (!x, !xs'), Nothing) | snd x <= maxV -> merge (maxV, xs', U.empty)
      (Just (!x, !xs'), Nothing) -> Just (x, (snd x, xs', U.empty))
      (Nothing, Just (!y, !ys')) | snd y <= maxV -> merge (maxV, U.empty, ys')
      (Nothing, Just (!y, !ys')) -> Just (y, (snd y, U.empty, ys'))
      (Just (!x, !xs'), Just (!y, !ys')) -> case compare (fst x) (fst y) of
        LT ->
          if snd x <= maxV
            then merge (maxV, xs', ys)
            else Just (x, (snd x, xs', ys))
        GT ->
          if snd y <= maxV
            then merge (maxV, xs, ys')
            else Just (y, (snd y, xs, ys'))
        EQ ->
          if maxV' == maxV
            then merge (maxV, xs', ys')
            else Just ((fst x, maxV'), (maxV', xs', ys'))
          where
            !maxV' = max (snd x) (snd y) `max` maxV

main :: IO ()
main = do
  ((!n, !maxW), !wvs) <- readInput
  print $ sparseListNotForced maxW wvs

提出情報

コンパイルエラー

app/Main.hs:1:1: warning: [-Wunused-imports]
    The import of ‘Control.DeepSeq’ is redundant
      except perhaps to import instances from ‘Control.DeepSeq’
    To import instances alone, use: import Control.DeepSeq()
  |
1 | import Control.DeepSeq
  | ^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:24:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘denseU’
   |
24 | denseU maxW = U.maximum . U.foldl' step s0
   | ^^^^^^

app/Main.hs:33:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘denseV’
   |
33 | denseV maxW = V.maximum . U.foldl' step s0
   | ^^^^^^

app/Main.hs:42:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘sparseList’
   |
42 | sparseList maxW = maximum . map snd . U.foldl' step s0
   | ^^^^^^^^^^

app/Main.hs:72:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘sparseIM’
   |
72 | sparseIM maxW = maximum . U.foldl' step s0
   | ^^^^^^^^

app/Main.hs:79:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘sparseU’
   |
79 | sparseU maxW = U.maximum . U.map snd . U.foldl' step s0
   | ^^^^^^^

app/Main.hs:96:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘sparseMonoList’
   |
96 | sparseMonoList maxW = maximum . map snd . U.foldl' step s0
   | ^^^^^^^^^^^^^^

app/Main.hs:119:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘sparseMonoU’
    |
119 | sparseMonoU maxW = U.maximum . U.map snd . U.foldl' step s0
    | ^^^^^^^^^^^

app/Main.hs:150:6: warning: [-Wunused-matches]
    Defined but not used: ‘n’
    |
150 |   ((!n, !maxW), !wvs) <- readInput
    |      ^

ジャッジ結果