結果

問題 No.4 おもりと天秤
ユーザー myuonmyuon
提出日時 2015-03-09 09:32:48
言語 Haskell
(9.8.2)
結果
AC  
実行時間 482 ms / 5,000 ms
コード長 681 bytes
コンパイル時間 2,122 ms
コンパイル使用メモリ 208,376 KB
実行使用メモリ 19,228 KB
最終ジャッジ日時 2023-09-08 16:10:28
合計ジャッジ時間 5,413 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,208 KB
testcase_01 AC 2 ms
7,196 KB
testcase_02 AC 5 ms
8,672 KB
testcase_03 AC 3 ms
7,516 KB
testcase_04 AC 4 ms
8,236 KB
testcase_05 AC 184 ms
16,092 KB
testcase_06 AC 2 ms
7,240 KB
testcase_07 AC 181 ms
16,064 KB
testcase_08 AC 22 ms
12,568 KB
testcase_09 AC 482 ms
19,228 KB
testcase_10 AC 222 ms
16,280 KB
testcase_11 AC 3 ms
7,524 KB
testcase_12 AC 2 ms
7,228 KB
testcase_13 AC 2 ms
7,280 KB
testcase_14 AC 2 ms
7,284 KB
testcase_15 AC 2 ms
7,248 KB
testcase_16 AC 3 ms
7,404 KB
testcase_17 AC 3 ms
7,176 KB
testcase_18 AC 482 ms
14,588 KB
testcase_19 AC 152 ms
14,860 KB
testcase_20 AC 142 ms
14,828 KB
testcase_21 AC 142 ms
15,104 KB
testcase_22 AC 143 ms
14,880 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

ソースコード

diff # 

import Control.Applicative
import Data.List
import Data.Array

solve ws = if solve' ws then "possible" else "impossible"

solve' ws = go ws arr where
  arr = listArray ((0,0),(length ws, sum ws `div` 2 + 1)) $ True : repeat False
  check m = (/= []) $ filter (\((_,w),v) -> 2 * w == sum ws && v == True) $ assocs m

  go [] m = check m
  go (x:xs) m
    | check m = True
    | otherwise = let m' = accum (||) m $ filter (\((k,w),_) -> 2 * w <= sum ws) $ fmap (\((k,w),v) -> ((k+1,w+x),v)) $ filter (\(_,v) -> v == True) $ assocs m in go xs m'

main = do
  _ <- getLine
  ws <- fmap (read :: String -> Int) . words <$> getLine
  putStrLn $ solve $ sortBy (\x y -> compare y x) $ ws
0