結果
問題 | No.4 おもりと天秤 |
ユーザー | satonakatakumi |
提出日時 | 2021-08-05 22:56:10 |
言語 | Haskell (9.8.2) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 2,441 bytes |
コンパイル時間 | 1,178 ms |
コンパイル使用メモリ | 239,356 KB |
実行使用メモリ | 7,768 KB |
最終ジャッジ日時 | 2023-10-14 21:42:26 |
合計ジャッジ時間 | 2,382 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
7,544 KB |
testcase_01 | AC | 3 ms
7,348 KB |
testcase_02 | AC | 2 ms
7,508 KB |
testcase_03 | AC | 3 ms
7,452 KB |
testcase_04 | AC | 2 ms
7,520 KB |
testcase_05 | AC | 4 ms
7,576 KB |
testcase_06 | AC | 2 ms
7,364 KB |
testcase_07 | AC | 5 ms
7,568 KB |
testcase_08 | AC | 3 ms
7,420 KB |
testcase_09 | AC | 6 ms
7,768 KB |
testcase_10 | AC | 5 ms
7,620 KB |
testcase_11 | AC | 2 ms
7,372 KB |
testcase_12 | AC | 3 ms
7,436 KB |
testcase_13 | AC | 2 ms
7,440 KB |
testcase_14 | AC | 2 ms
7,372 KB |
testcase_15 | AC | 2 ms
7,372 KB |
testcase_16 | AC | 2 ms
7,464 KB |
testcase_17 | AC | 3 ms
7,360 KB |
testcase_18 | AC | 4 ms
7,572 KB |
testcase_19 | AC | 4 ms
7,568 KB |
testcase_20 | AC | 4 ms
7,552 KB |
testcase_21 | AC | 4 ms
7,624 KB |
testcase_22 | AC | 4 ms
7,608 KB |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE DefaultSignatures #-} {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE DerivingVia #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE KindSignatures #-} {-# LANGUAGE RecordWildCards #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE UndecidableInstances #-} -- module Yukicoder.No4 where import Control.Monad import Control.Monad.Cont import Control.Monad.Fix import Control.Monad.ST import Control.Monad.State import Data.Bits import Data.Bool import Data.Char import Data.Coerce import qualified Data.Foldable as F import Data.Int import Data.IORef import qualified Data.List as L import Data.Maybe import Data.STRef import Data.Word import GHC.Exts import System.CPUTime import System.IO import Unsafe.Coerce import qualified Data.ByteString as BS import qualified Data.ByteString.Builder as BSB import qualified Data.ByteString.Char8 as BSC8 import qualified Data.ByteString.Unsafe as BSU import qualified Data.Vector as V import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Generic as VG import qualified Data.Vector.Generic.Mutable as VGM import qualified Data.Vector.Mutable as VM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM readInts :: Int -> IO (VU.Vector Int) readInts n = VU.unfoldrN n _f <$> BSC8.getLine where _f = runStateT (coerce $ BSC8.readInt . BSC8.dropWhile isSpace) main :: IO () main = do n <- readLn :: IO Int ws <- readInts n let s = VU.sum ws if odd s then putStrLn "impossible" else do let vec = f ws s if vec VU.! (s `div` 2) then putStrLn "possible" else putStrLn "impossible" f :: VU.Vector Int -> Int -> VU.Vector Bool f ws s = VU.create $ do dp <- VUM.unsafeNew 11111 VUM.unsafeWrite dp 0 True let t = s `div` 2 VU.forM_ ws $ \wi -> do forM_ [t, t - 1 .. 0] $ \j -> do dpj <- VUM.unsafeRead dp j when (j + wi <= s && dpj) $ VUM.unsafeWrite dp (j + wi) True return dp