Submission #1556179
Source Code Expand
import Data.List import Data.Maybe import Data.Function 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 m) 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]] m = fromListAccum h w $ zipWith (zipWith (&)) css $ tails $ cycle [id, negate] :: IMatrix balanced m (c1,c2,a) | rsum m c1 c2 == 0 = Just a | otherwise = Nothing type Height = Int type Width = Int type Coord = (Height, Width) type Index = Int -- 1-indexed data IMatrix = M { _height :: Int, _width :: Int, _matrix :: A.UArray Index Int } deriving (Eq, Show) (!) :: IMatrix -> 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]] -> IMatrix fromList h w = M h w . A.listArray (1, h * w) . concat fromListAccum :: Height -> Width -> [[Int]] -> IMatrix 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 :: IMatrix -> 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
Submission Time | |
---|---|
Task | B - チョコレート |
User | aimy |
Language | Haskell (GHC 7.10.3) |
Score | 100 |
Code Size | 1786 Byte |
Status | AC |
Exec Time | 1101 ms |
Memory | 4476 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt |
All | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample-01.txt | AC | 1 ms | 508 KB |
subtask0_sample-02.txt | AC | 1 ms | 380 KB |
subtask0_sample-03.txt | AC | 1 ms | 508 KB |
subtask0_sample-04.txt | AC | 1 ms | 508 KB |
subtask0_sample-05.txt | AC | 1 ms | 380 KB |
subtask1_01.txt | AC | 1 ms | 508 KB |
subtask1_02.txt | AC | 1 ms | 508 KB |
subtask1_03.txt | AC | 1 ms | 508 KB |
subtask1_04.txt | AC | 2 ms | 636 KB |
subtask1_05.txt | AC | 2 ms | 1020 KB |
subtask1_06.txt | AC | 4 ms | 1020 KB |
subtask1_07.txt | AC | 1 ms | 636 KB |
subtask1_08.txt | AC | 2 ms | 1020 KB |
subtask1_09.txt | AC | 344 ms | 4348 KB |
subtask1_10.txt | AC | 57 ms | 2300 KB |
subtask1_11.txt | AC | 259 ms | 4348 KB |
subtask1_12.txt | AC | 259 ms | 4348 KB |
subtask1_13.txt | AC | 260 ms | 4476 KB |
subtask1_14.txt | AC | 349 ms | 4348 KB |
subtask1_15.txt | AC | 357 ms | 4348 KB |
subtask1_16.txt | AC | 249 ms | 4476 KB |
subtask1_17.txt | AC | 278 ms | 4348 KB |
subtask1_18.txt | AC | 1 ms | 508 KB |
subtask1_19.txt | AC | 2 ms | 892 KB |
subtask1_20.txt | AC | 1101 ms | 4348 KB |