概要
n 項からなる単調非減少な数列が与えられる。
この数列の任意の項をちょうど k 回符号反転し、和を最大化したい。
得られる和の最大値を求めよ。
解法
まず、より小さい負数から順に符号を反転させます。
全ての負数を反転しても k が余る場合、残りの k が偶数であれば同一の数字を偶数回反転することで k を消費できます。
また、奇数の場合でも数列に 0 が存在すれば、k を消費することができます。
残りの k が奇数で、且つ 0 が無い場合は、最も小さい項の符号を反転することで k を消費します。
コード
import Control.Applicative import Control.Monad import Data.List main = do [ n, k ] <- map read . words <$> getLine as <- map read . words <$> getLine let negas = min ( length ( filter ( < 0 ) as ) ) k rest = ( k - negas ) `mod` 2 tmp = sort . change negas $ as res = if 0 `elem` tmp then sum tmp else sum $ change rest tmp print res change :: Int -> [Int] -> [Int] change _ [] = [] change 0 as = as change n (a:as) = a * ( -1 ) : change ( n - 1 ) as