結果

問題 No.286 Modulo Discount Store
ユーザー aimy
提出日時 2017-05-13 10:16:20
言語 Haskell
(8.6.2)
結果
AC  
実行時間 363 ms
コード長 722 Byte
コンパイル時間 1,467 ms
使用メモリ 46,516 KB
最終ジャッジ日時 2019-07-03 17:39:03

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 2 ms
6,868 KB
case2.txt AC 4 ms
6,868 KB
case3.txt AC 65 ms
13,744 KB
case4.txt AC 2 ms
6,872 KB
case5.txt AC 3 ms
6,872 KB
case6.txt AC 3 ms
6,868 KB
case7.txt AC 139 ms
19,888 KB
case8.txt AC 2 ms
6,872 KB
case9.txt AC 2 ms
6,868 KB
case10.txt AC 3 ms
6,872 KB
case11.txt AC 28 ms
7,868 KB
case12.txt AC 2 ms
6,868 KB
case13.txt AC 3 ms
8,916 KB
case14.txt AC 59 ms
13,748 KB
case15.txt AC 2 ms
6,872 KB
case16.txt AC 3 ms
8,912 KB
case17.txt AC 2 ms
6,872 KB
case18.txt AC 363 ms
46,516 KB
case19.txt AC 27 ms
7,864 KB
case20.txt AC 3 ms
6,868 KB
case21.txt AC 8 ms
6,868 KB
case22.txt AC 3 ms
8,916 KB
case23.txt AC 2 ms
6,868 KB
case24.txt AC 60 ms
13,744 KB
case25.txt AC 2 ms
8,920 KB
case26.txt AC 14 ms
6,868 KB
case27.txt AC 3 ms
6,872 KB
case28.txt AC 14 ms
8,916 KB
case29.txt AC 142 ms
19,884 KB
case30.txt AC 3 ms
6,872 KB
case31.txt AC 3 ms
6,872 KB
case32.txt AC 4 ms
6,872 KB
case33.txt AC 4 ms
8,912 KB
case34.txt AC 2 ms
6,868 KB
case35.txt AC 3 ms
6,872 KB
case36.txt AC 3 ms
6,872 KB
case37.txt AC 2 ms
6,868 KB
case38.txt AC 14 ms
6,872 KB
case39.txt AC 2 ms
6,872 KB
case40.txt AC 144 ms
19,880 KB
sample1.txt AC 3 ms
6,872 KB
sample2.txt AC 3 ms
6,868 KB
sample3.txt AC 3 ms
6,868 KB
テストケース一括ダウンロード
コンパイルメッセージ
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking a.out ...

ソースコード

diff #
import Data.IntMap ((!))
import qualified Data.IntMap as M
import Control.Monad
import Data.Bits

main = do
 n <- readLn
 ms <- map read . words <$> getContents
 print (mds n ms)

mds :: Int -> [Int] -> Int
mds n ms = snd $ M.findMax $ foldr (dp n ms t) (M.singleton 0 0) (replicate n [0..n-1])
 where 
  t = M.fromDistinctAscList $ do
   let es = map bit [0..n]
   bs <- replicateM n [0,1]
   let k = sum (zipWith (*) (reverse bs) es)
   let v = sum (zipWith (*) (reverse bs) ms) `mod` 1000
   return (k,v)

dp n ms t ds im = M.unionsWith min $ map buy ds
 where
  buy d = M.mapKeysMonotonic (flip setBit d) $ M.mapWithKey (\k v -> v + (max 0 ((ms!!d) - (t!k)))) $
          M.filterWithKey (\k _ -> not (testBit k d)) im
0