結果

問題 No.385 カップ麺生活
コンテスト
ユーザー はむ吉🐹
提出日時 2016-07-02 12:23:38
言語 Haskell
(9.10.1)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,407 bytes
コンパイル時間 9,954 ms
コンパイル使用メモリ 194,176 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-04 22:35:40
合計ジャッジ時間 7,889 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
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