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
Submission Time | |
---|---|
Task | D - おいしいたこ焼きの焼き方 |
User | hamadu |
Language | Haskell (GHC 7.4.1) |
Score | 100 |
Code Size | 1504 Byte |
Status | AC |
Exec Time | 636 ms |
Memory | 4340 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask1 | sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Subtask2 | rand0.txt, rand1.txt, rand2.txt, rand3.txt, rand4.txt, rand_max0.txt, rand_max1.txt, rand_max2.txt, rand_max3.txt, rand_max4.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
rand0.txt | AC | 269 ms | 3228 KB |
rand1.txt | AC | 182 ms | 3224 KB |
rand2.txt | AC | 265 ms | 3568 KB |
rand3.txt | AC | 84 ms | 3220 KB |
rand4.txt | AC | 28 ms | 2076 KB |
rand_max0.txt | AC | 636 ms | 4256 KB |
rand_max1.txt | AC | 630 ms | 4256 KB |
rand_max2.txt | AC | 631 ms | 4248 KB |
rand_max3.txt | AC | 633 ms | 4252 KB |
rand_max4.txt | AC | 628 ms | 4340 KB |
s1.txt | AC | 27 ms | 1812 KB |
s2.txt | AC | 24 ms | 1816 KB |
sub0.txt | AC | 26 ms | 1824 KB |
sub1.txt | AC | 27 ms | 1940 KB |
sub2.txt | AC | 26 ms | 1936 KB |
sub_rand_max0.txt | AC | 26 ms | 1824 KB |
sub_rand_max1.txt | AC | 26 ms | 1820 KB |
sub_rand_max2.txt | AC | 26 ms | 1820 KB |
sub_rand_max3.txt | AC | 26 ms | 1824 KB |
sub_rand_min0.txt | AC | 24 ms | 1692 KB |