Submission #1556176

---

Source Code Expand

import Data.List
import Data.Maybe
import qualified Data.Array.Base as A
import qualified Data.ByteString.Char8 as B

readInt :: B.ByteString -> Int
readInt = maybe undefined fst . B.readInt

readInts :: B.ByteString -> [Int]
readInts = map readInt . B.words

main = do
  [h,w] <- readInts <$> B.getLine
  css <- map readInts . B.lines <$> B.getContents
  print (chocolate h w css)

chocolate h w css = maximum $ (0 :) $ mapMaybe (balanced mb mw) coors
  where
    coors = [((x1,y1), (x2,y2), (x2-x1+1)*(y2-y1+1)) | x1<-[1..h], y1<-[1..w], x2<-[x1..h], y2<-[y1..w]]
    mb = fromListAccum h w $ zipWith (zipWith (*)) css $ tails $ cycle [0,1] :: Matrix
    mw = fromListAccum h w $ zipWith (zipWith (*)) css $ tails $ cycle [1,0] :: Matrix

balanced mb mw (c1,c2,a)
  | rsum mb c1 c2 == rsum mw c1 c2 = Just a
  | otherwise = Nothing


type Height = Int
type Width = Int
type Index = Int
type Coord = (Height, Width)

-- 1-indexed
data Matrix = M {
  _height :: Int,
  _width :: Int,
  _matrix :: A.UArray Index Int
} deriving (Eq, Show)

(!) :: Matrix -> Coord -> Int
(!) m c = A.unsafeAt (_matrix m) (idx (_width m) c - 1)

idx :: Width -> Coord -> Index
idx w (x, y) = (x - 1) * w + y

fromList :: Height -> Width -> [[Int]] -> Matrix
fromList h w = M h w . A.unsafeArray (1, h*w) . zip [0 ..] . concat

fromListAccum :: Height -> Width -> [[Int]] -> Matrix
fromListAccum h w = fromList h w . csum2

csum1 :: Num a => [a] -> [a]
csum1 = scanl1 (+)

csum2 :: Num a => [[a]] -> [[a]]
csum2 = transpose . map csum1 . transpose . map csum1

rsum :: Matrix -> Coord -> Coord -> Int
rsum m (x1,y1) c2@(x2,y2) = a1 - a2 - a3 + a4
  where
    a1 = m ! c2
    a2 = if x1 == 1 then 0 else m ! (x1-1, y2)
    a3 = if y1 == 1 then 0 else m ! (x2, y1-1)
    a4 = if x1 == 1 || y1 == 1 then 0 else m ! (x1-1, y1-1)

Submission Info

Judge Result