Submission #5487042

---

Source Code Expand

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 na h = (h `div` na, h `mod` na)

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

slvMemo :: Index -> Info2 -> Index -> Value
slvMemo (na, nb) d = fix (memorize na . 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)
  | ia == na-1 && ib == nb-1  = 0
  | True       && ib == nb-1  = f (ia+1, ib) + if myTurn i then da!ia else 0
  | ia == na-1 && 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

Judge Result