Submission #5488441


Source Code Expand

{-# OPTIONS_GHC -O2 #-}
import qualified Control.Monad as M
import Data.Array.Unboxed (Array(..), array, (!))
import Control.Monad.Fix (fix)

type Hash  = Int
type Index = (Int, Int)
type Value = Integer
type Info  = Array Int Value
type Info2 = (Info, Info)

main = do
    [na, nb] <- map read . words <$> getLine
    as <- map read . words <$> getLine
    bs <- map read . words <$> getLine
    print $ slvMemo (na, nb) (genArray na as, genArray nb bs) (0, 0)

genArray :: Int -> [Integer] -> Info
genArray n xs = array (0, n-1) [x | x <- zip [0..n] xs]

memorize :: Int -> (Index -> a) -> (Index -> a)
memorize n f i = map (f . hash2ix n) [0..] !! ix2hash n i

hash2ix :: Int -> Hash -> Index
hash2ix nb h = (h `div` (nb+1), h `mod` (nb+1))

ix2hash :: Int -> Index -> Hash
ix2hash nb (ia, ib) = ia * (nb+1) + ib

slvMemo :: Index -> Info2 -> Index -> Value
slvMemo (na, nb) d = fix (memorize nb . slv (na, nb) d)

myTurn :: Index -> Bool
myTurn (ia, ib) = even $ ia + ib

slv :: Index -> Info2 -> (Index -> Value) -> Index -> Value
slv (na, nb) (da, db) f i@(ia, ib)
  -- | trace (show (da,db) ++ "|" ++ show i ++ "|" ++ show (na,nb)) False            = 0
  | ia >  na || ib >  nb  = 0
  | ia == na && ib == nb  = 0
  | True     && ib == nb  = (f (ia+1, ib) + if myTurn i then da!ia else 0)
  | ia == na && True      = (f (ia, ib+1) + if myTurn i then db!ib else 0)
  | otherwise             = (if myTurn i then max pa pb else min pa pb) where
      pa = f (ia+1, ib) + if myTurn i then da!ia else 0
      pb = f (ia, ib+1) + if myTurn i then db!ib else 0

Submission Info

Submission Time
Task B - ゲーム
User ykarako
Language Haskell (GHC 7.10.3)
Score 0
Code Size 1605 Byte
Status TLE
Exec Time 2109 ms
Memory 92540 KB

Judge Result

Set Name All
Score / Max Score 0 / 3
Status
AC × 3
TLE × 2
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 2 ms 636 KB
01 TLE 2109 ms 92540 KB
02 TLE 2108 ms 86396 KB
90 AC 1 ms 508 KB
91 AC 1 ms 508 KB