結果

問題 No.50 おもちゃ箱
ユーザー satonakatakumisatonakatakumi
提出日時 2021-08-21 15:19:12
言語 Haskell
(9.8.2)
結果
WA  
実行時間 -
コード長 2,333 bytes
コンパイル時間 9,927 ms
コンパイル使用メモリ 248,332 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-23 06:28:52
合計ジャッジ時間 7,067 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 2 ms
6,940 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1 ms
6,944 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 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 # 

{-# LANGUAGE BangPatterns     #-}
{-# LANGUAGE TupleSections    #-}
{-# LANGUAGE TypeApplications #-}

import           Control.Monad
import           Control.Monad.State
import           Data.Bits
import qualified Data.ByteString.Char8             as BSC8
import           Data.Char
import           Data.Coerce
import qualified Data.Vector.Fusion.Stream.Monadic as VFSM
import qualified Data.Vector.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM

inf :: Int
inf = 1234567890
{-# INLINE inf #-}

main :: IO ()
main = do
  n <- readLn :: IO Int
  as <- seqInput n
  m <- readLn :: IO Int
  bs <- VU.reverse . bucketSort <$> seqInput m
  dp <- VUM.unsafeNew ((1 :: Int) `unsafeShiftL` n) :: IO (VUM.IOVector (Int, Int))
  VUM.unsafeWrite dp 0 (0, 0)
  forM_ [0 .. ((1 :: Int) `unsafeShiftL` n - 1)] $ \s -> forM_ [0 .. (n - 1)] $ \i -> when (s .&. ((1 :: Int) `unsafeShiftL` i) == 0) $ do
    (j, a) <- VUM.unsafeRead dp s
    if (j < m) && (a + as VU.! i <= bs VU.! j)
      then VUM.unsafeModify dp (min (j, a + as VU.! i)) (s + ((1 :: Int) `unsafeShiftL` i))
      else when ((j + 1 < m) && (as VU.! i <= bs VU.! (j + 1))) $  VUM.unsafeModify dp (min (j + 1, as VU.! i)) (s + ((1 :: Int) `unsafeShiftL` i))
  (ans, _) <- VUM.unsafeRead dp ((1 :: Int) `unsafeShiftL` n - 1)
  if ans < m
    then print $ ans + 1
    else putStrLn "-1"
  return ()


type Parser a = StateT BSC8.ByteString Maybe a
runParser :: Parser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString)
runParser = runStateT
{-# INLINE runParser #-}
int :: Parser Int
int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace
{-# INLINE int #-}
seqInput :: Int -> IO (VU.Vector Int)
seqInput n = VU.unfoldrN n (runParser int) <$> BSC8.getLine
{-# INLINE seqInput #-}
rev' :: Monad m => Int -> (Int -> m ()) -> m ()
rev' n = flip VFSM.mapM_ (streamR 0 (n + 1))
{-# INLINE rev' #-}
streamR :: Monad m => Int -> Int -> VFSM.Stream m Int
streamR !l !r = VFSM.Stream step (r - 1)
  where
    step x
      | x >= l = return $ VFSM.Yield x (x - 1)
      | otherwise = return VFSM.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] streamR #-}

bucketSort :: VU.Vector Int -> VU.Vector Int
bucketSort = VU.concatMap (uncurry $ flip VU.replicate) . VU.indexed . VU.unsafeAccumulate (+) (VU.replicate 21 0) . VU.map (,1)
{-# INLINE bucketSort #-}
0