Submission #1555009

---

Source Code Expand

import Data.List
import Data.Maybe
import qualified Data.Array.IArray 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]
    mw = fromListAccum h w $ zipWith (zipWith (*)) css $ tails $ cycle [1,0]

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 Coord = (Height, Width)

-- 1-indexed
type Matrix a = A.Array Height (A.Array Width a)

fromList :: Num a => Height -> Width -> [[a]] -> Matrix a
fromList h w = A.listArray (1, h) . map (A.listArray (1, w))

fromListAccum :: Num a => Height -> Width -> [[a]] -> Matrix a
fromListAccum h w = A.listArray (1, h) . map (A.listArray (1, w)) . csum2

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

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

(!) :: Matrix a -> Coord -> a
(!) m (x, y) = (m A.! x) A.! y

rsum :: Num a => Matrix a -> Coord -> Coord -> a
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