結果
問題 | No.31 悪のミックスジュース |
ユーザー | tottoripaper |
提出日時 | 2014-11-22 13:17:55 |
言語 | Haskell (9.8.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,034 bytes |
コンパイル時間 | 3,808 ms |
コンパイル使用メモリ | 188,564 KB |
実行使用メモリ | 13,188 KB |
最終ジャッジ日時 | 2023-08-30 22:12:44 |
合計ジャッジ時間 | 5,419 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | AC | 32 ms
12,852 KB |
testcase_05 | AC | 32 ms
12,936 KB |
testcase_06 | AC | 2 ms
7,664 KB |
testcase_07 | AC | 32 ms
12,876 KB |
testcase_08 | AC | 32 ms
12,912 KB |
testcase_09 | WA | - |
testcase_10 | AC | 3 ms
8,480 KB |
testcase_11 | WA | - |
testcase_12 | AC | 12 ms
12,288 KB |
testcase_13 | AC | 3 ms
7,880 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:18:11: warning: [GHC-97441] [-Woverflowed-literals] Literal 1001001001001001001001001 is out of the Int64 range -9223372036854775808..9223372036854775807 | 18 | inf = 1001001001001001001001001 | ^^^^^^^^^^^^^^^^^^^^^^^^^ [2 of 2] Linking a.out
ソースコード
import Control.Applicative import Data.List (sortBy) import Data.Int import Data.Array import qualified Data.Vector as V import Debug.Trace readInts :: IO [Int64] readInts = map read . words <$> getLine main = do [n, v] <- readInts cs <- readInts let comp (x,y) (x',y') = compare (x*y') (x'*y) total = sum cs cs' = V.fromList . sortBy comp $ zip (scanl1 (+) cs) [1..] inf = 1001001001001001001001001 dp x | x <= 0 = 0 | otherwise = table ! (n,x) where table = array ((0,0),(n,x)) [((i, j), f i j) | i <- [0..n], j <- [0..x]] f _ 0 = 0 f 0 _ = inf f i j = minimum [table!(i,j-1) + a, table!(i-1,j), if j-b >= 0 then table!(i,j-b) + a else inf] where (a, b) = cs' V.! (fromIntegral i-1) f i = a * ((v-n) `div` b) + dp ((v-n) `mod` b) where (a, b) = cs' V.! i in print $ if v < n then total else total + minimum (map f [0..fromIntegral n-1])