提出 #57301227 - AtCoder Beginner Contest 369

コンテスト時間: 2024-08-31 21:00:00+0900 ~ 2024-08-31 22:40:00+0900 (100分) AtCoderホームへ戻る

提出 #57301227

ソースコード拡げる

import Control.Monad
import Control.Monad.ST
import Control.Monad.Primitive
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Char
import Data.Ord
import Data.Ix
import Data.Bool
import Data.Vector.Unboxed.Base
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import Data.Array
import Data.Array.ST
import Data.Sequence (Seq)
import qualified Data.Sequence as Seq
import qualified Data.Set as Set
import Data.Tree
import qualified Data.Map as M
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap as IM
import qualified Data.Heap as H

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

putStrList xs = putStrLn . unwords $ map show xs

main = do
    n <- getInt
    as <- VU.fromList <$> getIntList
    
    let bnd = ((0, 0), (1, n))
        zero = minBound :: Int
        starts = [(0, n), (1, n)]
        v0s = [((0, 0), 0)]
        op1 = max
        op2 = (+)
        subproblems (t, i) | t == 0 && i == 1 = [((0, i-1), 0)]
                           | t == 1 && i == 1 = [((0, i-1), (as VU.! (i-1)))]
                           | t == 0 = [((1, i-1), (as VU.! (i-1)) * 2), ((0, i-1), 0)]
                           | t == 1 = [((0, i-1), (as VU.! (i-1))), ((1, i-1), 0)]
    let dparray = dpsolve bnd zero starts v0s op1 op2 subproblems
    print $ max (dparray ! (0, n)) (dparray ! (1, n))

    
    
dpsolve :: forall i e . (Ix i, Eq e) => 
            (i, i)                -- DPテーブルの始点、終点
             -> e                 -- DPテーブルの初期値（op1の零点）
             -> [i]               -- DPの開始の点のリスト
             -> [(i, e)]          -- DPテーブルの停止点（自明な点）
             -> (e -> e -> e)     -- op1 候補の統合演算
             -> (e -> e -> e)     -- op2 候補の算出演算
             -> (i -> [(i, e)])   -- 現在のindexから（小問題のindex,算出に使う値）のリスト
             -> Array i e
dpsolve bnd zero starts v0s op1 op2 subproblems = runSTArray $ do
    memo <- thaw $ accumArray op1 zero bnd v0s :: ST s (STArray s i e)
    forM_ starts $ \start -> go start memo
    return memo
        where
            go p memo = do
                    res <- readArray memo p
                    if res /= zero then return res
                    else do
                        ret <- foldM (\acc (sp, s) -> do
                                         spans <- go sp memo
                                         return $ acc `op1` (s `op2` spans))
                                         zero (subproblems p)
                        writeArray memo p ret
                        return ret

提出情報

提出日時	2024-08-31 21:31:50+0900
問題	D - Bonus EXP
ユーザ	pel
言語	Haskell (GHC 9.4.5)
得点	400
コード長	2960 Byte
結果	AC
実行時間	93 ms
メモリ	44924 KiB

コンパイルエラー

app/Main.hs:3:1: warning: [-Wunused-imports]
    The import of ‘Control.Monad.Primitive’ is redundant
      except perhaps to import instances from ‘Control.Monad.Primitive’
    To import instances alone, use: import Control.Monad.Primitive()
  |
3 | import Control.Monad.Primitive
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:6:1: warning: [-Wunused-imports]
    The import of ‘Data.List’ is redundant
      except perhaps to import instances from ‘Data.List’
    To import instances alone, use: import Data.List()
  |
6 | import Data.List
  | ^^^^^^^^^^^^^^^^

app/Main.hs:7:1: warning: [-Wunused-imports]
    The import of ‘Data.Char’ is redundant
      except perhaps to import instances from ‘Data.Char’
    To import instances alone, use: import Data.Char()
  |
7 | import Data.Char
  | ^^^^^^^^^^^^^^^^

app/Main.hs:8:1: warning: [-Wunused-imports]
    The import of ‘Data.Ord’ is redundant
      except perhaps to import instances from ‘Data.Ord’
    To import instances alone, use: import Data.Ord()
  |
8 | import Data.Ord
  | ^^^^^^^^^^^^^^^

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

app/Main.hs:11:1: warning: [-Wunused-imports]
    The import of ‘Data.Vector.Unboxed.Base’ is redundant
      except perhaps to import instances from ‘Data.Vector.Unboxed.Base’
    To import instances alone, use: import Data.Vector.Unboxed.Base()
   |
11 | import Data.Vector.Unboxed.Base
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

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

app/Main.hs:15:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.Vector.Mutable’ is redundant
      except perhaps to import instances from ‘Data.Vector.Mutable’
    To import instances alone, use: import Data.Vector.Mutable()
   |
15 | import qualified Data.Vector.Mutable as VM
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:18:1: warning: [-Wunused-imports]
    The import of ‘Data.Sequence’ is redundant
      except perhaps to import instances from ‘Data.Sequence’
    To import instances alone, use: import Data.Sequence()
   |
18 | import Data.Sequence (Seq)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^

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

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

app/Main.hs:21:1: warning: [-Wunused-imports]
    The import of ‘Data.Tree’ is redundant
      except perhaps to import instances from ‘Data.Tree’
    To import instances alone, use: import Data.Tree()
   |
21 | import Data.Tree
   | ^^^^^^^^^^^^^^^^

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

app/Main.hs:23:1: warning: [-Wunused-imports]
    The import of ‘Data.IntMap.Strict’ is redundant
      except perhaps to import instances from ‘Data.IntMap.Strict’
    To import instances alone, use: import Data.IntMap.Strict()
   |
23 | import Data.IntMap.Strict (IntMap)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

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

app/Main.hs:27:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature:
      readInt :: BS.ByteString -> Int
   |
27 | readInt = fst . fromJust . BS.readInt
   | ^^^^^^^

app/Main.hs:28:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature:
      readIntList :: BS.ByteString -> [Int]
   |
28 | readIntList = map readInt . BS.words
   | ^^^^^^^^^^^

app/Main.hs:29:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: getInt :: IO Int
   |
29 | getInt = readInt <$> BS.getLine
   | ^^^^^^

app/Main.hs:30:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: getIntList :: IO [Int]
   |
30 | getIntList = readIntList <$> BS.getLine
   | ^^^^^^^^^^

app/Main.hs:32:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature:
      putStrList :: Show a => [a] -> IO ()
   |
32 | putStrList xs = putStrLn . unwords $ map show xs
   | ^^^^^^^^^^

app/Main.hs:32:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘putStrList’
   |
32 | putStrList xs = putStrLn . unwords $ map show xs
   | ^^^^^^^^^^

app/Main.hs:34:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: main :: IO ()
   |
34 | main = do
   | ^^^^

app/Main.hs:44:9: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘subproblems’:
        Patterns of type ‘(a, Int)’ not matched: (_, _)
   |
44 |         subproblems (t, i) | t == 0 && i == 1 = [((0, i-1), 0)]
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

app/Main.hs:49:26: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Ix a0) arising from a use of ‘!’ at app/Main.hs:49:26
        (Num a0) arising from the literal ‘0’ at app/Main.hs:49:29
        (Num a0) arising from the literal ‘0’ at app/Main.hs:41:18
        (Num a0) arising from the literal ‘0’ at app/Main.hs:40:20
        (Num a0) arising from the literal ‘0’ at app/Main.hs:38:17
        (Ix a0) arising from a use of ‘dpsolve’ at app/Main.hs:48:19-25
        (Eq a0) arising from a use of ‘subproblems’ at app/Main.hs:48:55-65
        (Num a0)
          arising from a use of ‘subproblems’ at app/Main.hs:48:55-65
    • In the first argument of ‘max’, namely ‘(dparray ! (0, n))’
      In the second argument of ‘($)’, namely
        ‘max (dparray ! (0, n)) (dparray ! (1, n))’
      In a stmt of a 'do' block:
        print $ max (dparray ! (0, n)) (dparray ! (1, n))
   |
49 |     print $ max (dparray ! (0, n)) (dparray ! (1, n))
   |                          ^

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

400 / 400

結果

× 2

× 49

セット名	テストケース
Sample	example_00.txt, example_01.txt
All	example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt

ケース名	結果	実行時間	メモリ
example_00.txt	AC	2 ms	6512 KiB
example_01.txt	AC	2 ms	6736 KiB
hand_00.txt	AC	62 ms	43368 KiB
hand_01.txt	AC	62 ms	42884 KiB
hand_02.txt	AC	2 ms	6672 KiB
hand_03.txt	AC	72 ms	43460 KiB
hand_04.txt	AC	72 ms	44136 KiB
hand_05.txt	AC	72 ms	44144 KiB
hand_06.txt	AC	1 ms	6512 KiB
random_00.txt	AC	62 ms	43940 KiB
random_01.txt	AC	62 ms	44600 KiB
random_02.txt	AC	62 ms	44140 KiB
random_03.txt	AC	72 ms	43932 KiB
random_04.txt	AC	72 ms	44716 KiB
random_05.txt	AC	72 ms	44924 KiB
random_06.txt	AC	62 ms	43720 KiB
random_07.txt	AC	72 ms	44228 KiB
random_08.txt	AC	62 ms	43488 KiB
random_09.txt	AC	72 ms	44780 KiB
random_10.txt	AC	72 ms	44008 KiB
random_11.txt	AC	72 ms	42936 KiB
random_12.txt	AC	62 ms	43832 KiB
random_13.txt	AC	72 ms	43524 KiB
random_14.txt	AC	72 ms	44124 KiB
random_15.txt	AC	72 ms	44032 KiB
random_16.txt	AC	72 ms	44520 KiB
random_17.txt	AC	72 ms	44212 KiB
random_18.txt	AC	72 ms	43160 KiB
random_19.txt	AC	72 ms	43196 KiB
random_20.txt	AC	72 ms	43364 KiB
random_21.txt	AC	82 ms	44180 KiB
random_22.txt	AC	82 ms	43348 KiB
random_23.txt	AC	72 ms	43188 KiB
random_24.txt	AC	72 ms	43408 KiB
random_25.txt	AC	72 ms	43408 KiB
random_26.txt	AC	72 ms	43188 KiB
random_27.txt	AC	92 ms	43384 KiB
random_28.txt	AC	82 ms	43412 KiB
random_29.txt	AC	72 ms	43340 KiB
random_30.txt	AC	72 ms	44860 KiB
random_31.txt	AC	72 ms	44884 KiB
random_32.txt	AC	93 ms	44852 KiB
random_33.txt	AC	72 ms	44872 KiB
random_34.txt	AC	72 ms	44884 KiB
random_35.txt	AC	72 ms	44916 KiB
random_36.txt	AC	72 ms	44880 KiB
random_37.txt	AC	72 ms	44800 KiB
random_38.txt	AC	72 ms	44860 KiB
random_39.txt	AC	72 ms	44812 KiB