Submission #72597369


Source Code Expand

{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE NegativeLiterals #-}
{-# LANGUAGE HexFloatLiterals #-}
{-# LANGUAGE NumericUnderscores #-}

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE BlockArguments #-}
-- {-# LANGUAGE OverloadedLists #-}   
{-# LANGUAGE OverloadedStrings #-}   

{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeApplications #-}   

{-# OPTIONS_GHC -O2 #-}
{-# OPTIONS_GHC -Wno-tabs #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.Extra
import Control.Monad.ST

import Data.Bool
import Data.Bits
import Data.Char

import Data.Tuple.Extra hiding ( (&&&), (***) )
import Data.List hiding ( (!?) )
import Data.List.Extra hiding ( (!?) )
import Data.Maybe
import Data.Either
import Data.Function

import qualified Data.Set as Set
import qualified Data.IntSet as ISet
import qualified Data.Map as Map
import qualified Data.IntMap as IMap
import qualified Data.Sequence as Seq
import Data.Sequence ( (<|), (|>), (><), ViewL(..), ViewR(..) )

import qualified Data.ByteString.Char8 as B

import Data.Array
import Data.Array.ST.Safe
import Data.Array.MArray
import Data.STRef

import Text.Printf
import Debug.Trace

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Unboxed.Mutable as MV
-- import qualified Data.Vector.Unboxed.Mutable as MUV 

readInt = fst . fromJust . B.readInt <$> B.getLine
readInteger = fst . fromJust . B.readInteger <$> B.getLine
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine
readStr = trim . B.unpack <$> B.getLine
readStrs = map B.unpack . B.words <$> B.getLine

yesno = bool "No" "Yes"
mp [ a, b ] = ( a, b )

count a as = length $ filter ( == a ) as
countIf f as = length $ filter f as

swapArrayElem a i j = do
	x <- readArray a i
	y <- readArray a j
	writeArray a i y
	writeArray a j x

a !? i
	| inRange ( bounds a ) i = Just $ a ! i
	| otherwise = Nothing

printList :: Show a => [a] -> IO ()
printList = putStrLn . intercalate " " . map show

main = do
	[ n, m ] <- readInts
	[ ps, vs ] <- transpose <$> replicateM n readInts
	let
		idx ( i, j ) = i * ( m + 1 ) + j
		solve ps vs = runST do
			dp <- MV.replicate ( ( n + 1 ) * ( m + 1 ) ) ( minBound `div` 2 ) :: ST s ( MV.MVector s Int )
-- 			writeArray dp ( 0, 0 ) 0
			MV.unsafeWrite dp ( idx ( 0, 0 ) ) 0
			forM_ ( zip3 [ 0 .. ] ps vs ) $ \( i, p, v ) -> do
				forM_ [ 0 .. m ] $ \j -> do
-- 					modifyArray dp ( i + 1, j ) =<< max <$> readArray dp ( i, j )
					flip ( MV.unsafeModify dp ) ( idx ( i + 1, j ) ) =<< max <$> MV.unsafeRead dp ( idx ( i, j ) )
					when ( j + p <= m ) do
-- 						modifyArray dp ( i + 1, j + p ) =<< max . ( v + ) <$> readArray dp ( i, j )
						flip ( MV.unsafeModify dp ) ( idx ( i + 1, j + p ) ) =<< max . ( v + ) <$> MV.unsafeRead dp ( idx ( i, j ) )
			forM_ [ 0 .. n ] $ \i -> do
				forM_ [ 1 .. m ] $ \j -> do
-- 					modifyArray dp ( i, j ) =<< max <$> readArray dp ( i, j - 1 )
					flip ( MV.unsafeModify dp ) ( idx ( i, j ) ) =<< max <$> MV.unsafeRead dp ( idx ( i, j - 1 ) )
-- 
			UV.unsafeFreeze dp
		dp1 = solve ps vs
		dp2 = solve ( reverse ps ) ( reverse vs )
		ma = maximum do
			j <- [ 0 .. m ]
			return $ dp1 UV.! idx ( n, j )
		f True False = 'A'
		f True True = 'B'
		f _ _ = 'C'
	putStrLn $ map ( uncurry f ) do
		( i, p, v ) <- zip3 [ 0 .. ] ps vs
		let
			inc = or do
				j <- [ 0 .. m - p ]
				return $ dp1 UV.! idx ( i, j ) + dp2 UV.! idx ( n - 1 - i, m - p - j ) + v == ma
			exc = or do
				j <- [ 0 .. m ]
				return $ dp1 UV.! idx ( i, j ) + dp2 UV.! idx ( n - 1 - i, m - j ) == ma
		return ( inc, exc )

Submission Info

Submission Time
Task F - Must Buy
User torus711
Language Haskell (GHC 9.8.4)
Score 500
Code Size 3951 Byte
Status AC
Exec Time 923 ms
Memory 796436 KiB

Compile Error

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

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

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

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

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

app/Main.hs:30:1: warning: [GHC-66111] [-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()
   |
30 | import Data.Char
   | ^^^^^^^^^^^^^^^^

app/Main.hs:32:1: warning: [GHC-66111] [-Wunused-imports]
    The import of ‘Data.Tuple.Extra’ is redundant
      except perhaps to import instances from ‘Data.Tuple.Extra’
    To import instances alone, use: import Data.Tuple.Extra()
   |
32 | import Data.Tuple.Extra hiding ( (&&&), (***) )
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

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

app/Main.hs:39:1: warning: [GHC-66111] [-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()
   |
39 | import qualified Data.Set as Set
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

app/Main.hs:41:1: warning: [GHC-66111] [-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()
   |
41 | import qualified Data.Map as Map
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:42:1: warning: [GHC-66111] [-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()
   |
42 | import qualified Data.IntMap as IMap
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:43:1: warning: [GHC-66111] [-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()
   |
43 | import qualified Data.Sequence as Seq
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:44:1: warning: [GHC-66111] [-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()
   |
44 | import Data.Sequence ( (<|), (|>), (><), ViewL(..), ViewR(..) )
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

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

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

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

app/Main.hs:56:1: warning: [GHC-66111] [-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()
   |
56 | import qualified Data.Vector as V
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:61:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature: readInt :: IO Int
   |
61 | readInt = fst . fromJust . B.readInt <$> B.getLine
   | ^^^^^^^

app/Main.hs:61:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘readInt’
   |
61 | readInt = fst . fromJust . B.readInt <$> B.getLine
   | ^^^^^^^

app/Main.hs:62:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature: readInteger :: IO Integer
   |
62 | readInteger = fst . fromJust . B.readInteger <$> B.getLine
   | ^^^^^^^^^^^

app/Main.hs:62:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘readInteger’
   |
62 | readInteger = fst . fromJust . B.readInteger <$> B.getLine
   | ^^^^^^^^^^^

app/Main.hs:63:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature: readInts :: IO [Int]
   |
63 | readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
   | ^^^^^^^^

app/Main.hs:64:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature:
      readIntegers :: IO [Integer]
   |
64 | readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine
   | ^^^^^^^^^^^^

app/Main.hs:64:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘readIntegers’
   |
64 | readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine
   | ^^^^^^^^^^^^

app/Main.hs:65:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature: readStr :: IO String
   |
65 | readStr = trim . B.unpack <$> B.getLine
   | ^^^^^^^

app/Main.hs:65:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘readStr’
   |
65 | readStr = trim . B.unpack <$> B.getLine
   | ^^^^^^^

app/Main.hs:66:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature: readStrs :: IO [[Char]]
   |
66 | readStrs = map B.unpack . B.words <$> B.getLine
   | ^^^^^^^^

app/Main.hs:66:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘readStrs’
   |
66 | readStrs = map B.unpack . B.words <$> B.getLine
   | ^^^^^^^^

app/Main.hs:68:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature: yesno :: Bool -> String
   |
68 | yesno = bool "No" "Yes"
   | ^^^^^

app/Main.hs:68:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘yesno’
   |
68 | yesno = bool "No" "Yes"
   | ^^^^^

app/Main.hs:68:14: warning: [GHC-18042] [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘String’ in the following constraint
        Data.String.IsString a0 arising from the literal ‘"No"’
    • In the first argument of ‘bool’, namely ‘"No"’
      In the expression: bool "No" "Yes"
      In an equation for ‘yesno’: yesno = bool "No" "Yes"
   |
68 | yesno = bool "No" "Yes"
   |              ^^^^

app/Main.hs:69:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature: mp :: [b] -> (b, b)
   |
69 | mp [ a, b ] = ( a, b )
   | ^^

app/Main.hs:69:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘mp’
   |
69 | mp [ a, b ] = ( a, b )
   | ^^

app/Main.hs:69:1: warning: [GHC-62161] [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘mp’:
        Patterns of type ‘[b]’ not matched:
            []
            [_]
            (_:_:_:_)
   |
69 | mp [ a, b ] = ( a, b )
   | ^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:71:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature:
      count :: Eq a => a -> [a] -> Int
   |
71 | count a as = length $ filter ( == a ) as
   | ^^^^^

app/Main.hs:71:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘count’
   |
71 | count a as = length $ filter ( == a ) as
   | ^^^^^

app/Main.hs:72:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature:
      countIf :: (a -> Bool) -> [a] -> Int
   |
72 | countIf f as = length $ filter f as
   | ^^^^^^^

app/Main.hs:72:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘countIf’
   |
72 | countIf f as = length $ filter f as
   | ^^^^^^^

app/Main.hs:74:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature:
      swapArrayElem :: (MArray a e m, Ix i) => a i e -> i -> i -> m ()
   |
74 | swapArrayElem a i j = do
   | ^^^^^^^^^^^^^

app/Main.hs:74:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘swapArrayElem’
   |
74 | swapArrayElem a i j = do
   | ^^^^^^^^^^^^^

app/Main.hs:80:3: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature:
      (!?) :: Ix i => Array i a -> i -> Maybe a
   |
80 | a !? i
   |   ^^

app/Main.hs:80:3: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘!?’
   |
80 | a !? i
   |   ^^

app/Main.hs:85:1: warning: [GHC-40910] [-Wunused-top-binds]
    Defined but not used: ‘printList’
   |
85 | printList = putStrLn . intercalate " " . map show
   | ^^^^^^^^^

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

app/Main.hs:92:23: warning: [GHC-63397] [-Wname-shadowing]
    This binding for ‘ps’ shadows the existing binding
      bound at app/Main.hs:89:11
   |
92 |                 solve ps vs = runST do
   |                       ^^

app/Main.hs:92:26: warning: [GHC-63397] [-Wname-shadowing]
    This binding for ‘vs’ shadows the existing binding
      bound at app/Main.hs:89:15
   |
92 |                 solve ps vs = runST do
   |                          ^^
Configuration is affected by the following files:
- cabal.project
- cabal.project.freeze
- cabal.project.local

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 50
Set Name Test Cases
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, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, hand_14.txt, hand_15.txt, hand_16.txt, hand_17.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
Case Name Status Exec Time Memory
example_00.txt AC 6 ms 8788 KiB
example_01.txt AC 2 ms 8568 KiB
hand_00.txt AC 860 ms 796124 KiB
hand_01.txt AC 702 ms 796032 KiB
hand_02.txt AC 635 ms 795980 KiB
hand_03.txt AC 622 ms 796052 KiB
hand_04.txt AC 615 ms 796436 KiB
hand_05.txt AC 236 ms 264644 KiB
hand_06.txt AC 697 ms 796108 KiB
hand_07.txt AC 68 ms 88336 KiB
hand_08.txt AC 675 ms 796368 KiB
hand_09.txt AC 814 ms 796112 KiB
hand_10.txt AC 613 ms 795980 KiB
hand_11.txt AC 625 ms 796020 KiB
hand_12.txt AC 8 ms 16184 KiB
hand_13.txt AC 6 ms 15512 KiB
hand_14.txt AC 17 ms 25616 KiB
hand_15.txt AC 852 ms 796212 KiB
hand_16.txt AC 759 ms 796172 KiB
hand_17.txt AC 707 ms 796132 KiB
random_00.txt AC 690 ms 792528 KiB
random_01.txt AC 685 ms 787300 KiB
random_02.txt AC 686 ms 791672 KiB
random_03.txt AC 44 ms 51952 KiB
random_04.txt AC 33 ms 44196 KiB
random_05.txt AC 230 ms 230512 KiB
random_06.txt AC 180 ms 185500 KiB
random_07.txt AC 431 ms 414928 KiB
random_08.txt AC 392 ms 390044 KiB
random_09.txt AC 801 ms 764604 KiB
random_10.txt AC 836 ms 793940 KiB
random_11.txt AC 839 ms 791564 KiB
random_12.txt AC 900 ms 790916 KiB
random_13.txt AC 923 ms 794716 KiB
random_14.txt AC 917 ms 795504 KiB
random_15.txt AC 622 ms 790420 KiB
random_16.txt AC 636 ms 784912 KiB
random_17.txt AC 675 ms 783736 KiB
random_18.txt AC 671 ms 790540 KiB
random_19.txt AC 691 ms 794492 KiB
random_20.txt AC 676 ms 784080 KiB
random_21.txt AC 708 ms 789956 KiB
random_22.txt AC 704 ms 784236 KiB
random_23.txt AC 830 ms 790716 KiB
random_24.txt AC 820 ms 795156 KiB
random_25.txt AC 639 ms 792460 KiB
random_26.txt AC 633 ms 785264 KiB
random_27.txt AC 678 ms 784340 KiB
random_28.txt AC 686 ms 784708 KiB
random_29.txt AC 695 ms 794376 KiB