Submission #40785503

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import Data.Array
import Data.List
import qualified Data.IntSet as IS
main = do
  [h,w,t] <- getLnInts
  sss <- replicateM h getLnInts
  let ans = abc298g h w t sss
  print ans
getLnInts :: IO [Int]
getLnInts = map read . words <$> getLine
abc298g :: Int -> Int -> Int -> [[Int]] -> Int
abc298g h w t sss = minimum
    [ res - lower
    | lower <- IS.elems lowers
    , let res = solve lower
    , res >= lower
    ]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Control.Monad
import Data.Array
import Data.List
import qualified Data.IntSet as IS

main = do
  [h,w,t] <- getLnInts
  sss <- replicateM h getLnInts
  let ans = abc298g h w t sss
  print ans

getLnInts :: IO [Int]
getLnInts = map read . words <$> getLine

abc298g :: Int -> Int -> Int -> [[Int]] -> Int
abc298g h w t sss = minimum
    [ res - lower
    | lower <- IS.elems lowers
    , let res = solve lower
    , res >= lower
    ]
  where
    h1 = succ h
    w1 = succ w
    accs = listArray ((1,1),(h1,w1)) $ concat $
           scanl (zipWith (+)) (replicate w1 0) $
           map (scanl (+) 0) sss
-- 上を含まない範囲指定
    berries u d l r = accs ! (d,r) + accs ! (u,l) - accs ! (d,l) - accs ! (u,r)
    lowers = IS.fromList
      [ berries u d l r
      | u <- [1..h], d <- [succ u..h1]
      , l <- [1..w], r <- [succ l..w1]
      ]
    t1 = succ t
    solve lower = arr ! (1,h1,1,w1,t1)
      where
        bnds = ((1,2,1,2,1),(h,h1,w,w1,t1))
        arr = listArray bnds $ map f $ range bnds
        f (u,d,l,r,c)
          | c == 1    = if b < lower then -1 else b
          | null recs = -1
          | otherwise = minimum recs
          where
            b = berries u d l r
            recs =
              [ max a1 a2
              | m <- [succ u..pred d], cc <- [1..pred c]
              , let a1 = arr ! (u, m, l, r, cc), a1 >= lower
              , let a2 = arr ! (m, d, l, r, c - cc), a2 >= lower
              ] ++
              [ max a1 a2
              | m <- [succ l..pred r], cc <- [1..pred c]
              , let a1 = arr ! (u, d, l, m, cc), a1 >= lower
              , let a2 = arr ! (u, d, m, r, c - cc), a2 >= lower
              ]

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result