Submission #70805806

---

Source Code Expand

{-# OPTIONS_GHC -Wall #-}
{-# OPTIONS_GHC -Wname-shadowing #-} -- 内側のスコープの値と同じ名前が外側のスコープにあるとき警告する

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import Data.Array.Unboxed qualified as A
import Data.ByteString.Char8 qualified as BS
import Control.Monad.ST -- runST / ST s で使用
import Data.Array.ST -- STUArray で使用
import qualified Data.Array.MArray as AM


readInts :: IO [Int]
readInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

{-
 - #DP 方針は時間内に立てられたが残り1分なので諦めた
 -}

main :: IO ()
main = do
  n <- readLn :: IO Int
  whbs <- replicateM n $ do
    [w,h,b] <- readInts
    return (w,h,b)
  let wSum = sum $ map (\(w,h,b) -> w) whbs
  let wSum_2 = wSum `div` 2
  print $ maximum $ solve n wSum_2 whbs

solve :: Int -> Int -> [(Int,Int,Int)] -> [Int] -- A.UArray (Int,Int) Int
solve n wSum_2 whbs = runST $ do
  arr <- AM.newArray ((0,0),(n,wSum_2)) (minBound::Int) :: ST s (STUArray s (Int,Int) Int) -- 型に注意
  AM.writeArray arr (0,0) 0 -- DPテーブルの初期値設定
  forM_ [0..n-1] $ \i -> do
    let (w,h,b) = whbs !! i
    forM_ [0..wSum_2] $ \j -> do
      val0 <- AM.readArray arr (i,j)
      when (val0 /= (minBound::Int)) $ do
        when ( j+w <= wSum_2 ) $ do
          val1 <- AM.readArray arr (i+1,j+w)
          AM.writeArray arr (i+1,j+w) $ max val1 (val0 + h)
        when ( j <= wSum_2 ) $ do
          val1 <- AM.readArray arr (i+1,j)
          AM.writeArray arr (i+1,j) $ max val1 (val0 + b)
  forM [0..wSum_2] $ \j -> do
    val <- AM.readArray arr (n,j)
    return val

Submission Info

Compile Error

Configuration is affected by the following files:
- cabal.project
- cabal.project.freeze
- cabal.project.local

app/Main.hs:9:1: warning: [GHC-66111] [-Wunused-imports]
    The qualified import of ‘Data.Array.Unboxed’ is redundant
      except perhaps to import instances from ‘Data.Array.Unboxed’
    To import instances alone, use: import Data.Array.Unboxed()
  |
9 | import Data.Array.Unboxed qualified as A
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:10:1: warning: [GHC-66111] [-Wunused-imports]
    The qualified import of ‘Data.ByteString.Char8’ is redundant
      except perhaps to import instances from ‘Data.ByteString.Char8’
    To import instances alone, use: import Data.ByteString.Char8()
   |
10 | import Data.ByteString.Char8 qualified as BS
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:29:29: warning: [GHC-40910] [-Wunused-matches]
    Defined but not used: ‘h’
   |
29 |   let wSum = sum $ map (\(w,h,b) -> w) whbs
   |                             ^

app/Main.hs:29:31: warning: [GHC-40910] [-Wunused-matches]
    Defined but not used: ‘b’
   |
29 |   let wSum = sum $ map (\(w,h,b) -> w) whbs
   |                               ^
Configuration is affected by the following files:
- cabal.project
- cabal.project.freeze
- cabal.project.local

Judge Result