結果

問題 No.385 カップ麺生活
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-07-02 12:23:38
言語 Haskell
(9.8.2)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,407 bytes
コンパイル時間 5,803 ms
コンパイル使用メモリ 196,736 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-15 07:30:21
合計ジャッジ時間 6,816 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 5 ms
6,940 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 3 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 3 ms
6,944 KB
testcase_21 AC 3 ms
6,944 KB
testcase_22 AC 3 ms
6,944 KB
testcase_23 AC 4 ms
6,940 KB
testcase_24 AC 3 ms
6,940 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 3 ms
6,940 KB
testcase_27 AC 3 ms
6,940 KB
testcase_28 AC 3 ms
6,944 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 3 ms
6,940 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 3 ms
6,944 KB
testcase_34 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

import Control.Applicative
import Control.Monad
import Data.Array.ST
import Data.Array.Unboxed
import Data.Int

inf :: Integral a => a
inf = 1000000000

-- Based on <http://qiita.com/little_Haskeller/items/614a3ae20a517c19bb1f this article> .
primes2 :: Integral a => [a]
primes2 = [2, 3, 5] ++ sieve2 5 7 (drop 2 primes2)
    where
        sieve2 m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ sieve2 (m * p) (p * p) ps
            where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
        sieve2 _ _ [] = error "Unexpected"

-- Based on <https://wiki.haskell.org/Testing_primality this page> .
isPrime2 :: Integral a => a -> Bool
isPrime2 n = n > 1 && foldr (\p r -> p * p > n || (mod n p /= 0 && r)) True primes2

dpTable :: Int64 -> [Int64] -> UArray Int64 Int64
dpTable m cs = runSTUArray $ do
    dp <- newArray (0, m) (-inf)
    writeArray dp m 0
    forM_ cs $ \c ->
        forM_ [m - c, m - c - 1 .. 0] $ \i -> do
            term1 <- readArray dp i
            term2 <- readArray dp $ i + c
            writeArray dp i $ max term1 $ term2 + 1
    return dp

computeMaxCups :: Int64 -> [Int64] -> Int64
computeMaxCups m cs = s + maximum (elems dp)
    where
        dp = dpTable m cs
        s = sum [d | i <- [1 .. m], let d = dp ! i, d > 0, isPrime2 i]

main :: IO ()
main = do
    m <- readLn
    _ <- getLine
    cs <- fmap read . words <$> getLine
    print $ computeMaxCups m cs
0