Submission #227392

---

Source Code Expand

import Control.Applicative
import Control.Monad
import qualified Data.Vector as V
import qualified Data.Vector.Storable as VS
import qualified Data.List as L
import qualified Data.Map as M

type Imos = V.Vector (V.Vector Int)

main :: IO ()
main = do
  n <- getInt
  d <- replicateM n getInts
  q <- getInt
  p <- replicateM q getInt
  putStr $ solve d p

solve :: [[Int]] -> [Int] -> String
solve d p = unlines $ map (show . (\x -> tbl VS.! x)) p 
  where tbl = buildMax $ buildArea $ buildImos d

buildMax :: VS.Vector Int -> VS.Vector Int
buildMax v = VS.tail $ VS.scanl (\acc x -> max acc x) 0 v

buildArea :: Imos -> VS.Vector Int
buildArea imos = VS.accum max sum rng
  where
    sum = VS.replicate 2525 0
    n = (V.length imos) - 1
    rng = do
      fx <- [0..n]
      tx <- [fx+1..n]
      fy <- [0..n]
      ty <- [fy+1..n]
      return ((ty-fy)*(tx-fx), (imos V.! ty V.! tx) - (imos V.! fy V.! tx) - (imos V.! ty V.! fx) + (imos V.! fy V.! fx))

buildImos :: [[Int]] -> Imos
buildImos d = imos
  where
    n = length d
    imos = V.generate (n+1) (\y -> 
             V.generate (n+1) (\x -> 
               range y x
             )
           )
    range :: Int -> Int -> Int
    range 0 _ = 0
    range _ 0 = 0
    range i j =
      (imos V.! (i-1) V.! j) + (imos V.! i V.! (j-1)) - (imos V.! (i-1) V.! (j-1)) + (d !! (i-1) !! (j-1))

getInt :: IO (Int)
getInt = readLn

getInts :: IO ([Int])
getInts = map read <$> words <$> getLine

Submission Info

Judge Result