Submission #1759031

---

Source Code Expand

import Control.Monad

type Board = [[Int]]

rectBoards :: Board -> (Int, Int) -> [(Int, Int)]
rectBoards board (m, n) = do
    let d = length board
    a <- [0 .. (d - 1)]
    b <- [0 .. (d - 1)]
    guard (a + m <= d)
    guard (b + n <= d)
    return (a, b)

rectangles :: Int -> [(Int, Int)]
rectangles s = do
    a <- [1 .. s]
    b <- [1 .. s `div `a]
    guard (a * b <= s)
    return (a, b)

score :: Board -> Int -> Int -> Int -> Int -> Int
score board x y m n = sum
    [(board !! j) !! i | i <- [x .. (x + m - 1)], j <- [y .. (y + n - 1)]]

scores :: Board -> [(Int, Int)] -> [(Int, Int)] -> [Int]
scores board rbs rs = do
    let d = length board
    (x,y) <- rbs
    (m,n) <- rs
    guard (x + m <= d)
    guard (y + n <= d)
    return $ score board x y m n

maxScore :: Board -> Int -> Int
maxScore board rsize =
    let rects = rectangles rsize
    in maximum $ maximum $ map (\r -> scores board (rectBoards board r) rects) rects

main :: IO ()
main = do
    n <- readLn
    board <- mapM (\_ -> map (read :: String -> Int) . words <$> getLine) [1..n]
    q <- readLn
    mapM_ (\_ -> do
        p <- readLn :: IO Int
        print $ maxScore board p
        ) [1..q]

Submission Info

Judge Result