提出 #576251

---

ソースコード 拡げる

import Control.Applicative
import Data.Monoid
import Data.List
import Data.Foldable (fold)
import Debug.Trace
 
data Max a b = Max !a b | NoMax
 
instance (Ord a, Monoid b) => Monoid (Max a b) where
  mempty = NoMax
  mappend (Max a xs) (Max b ys) = case compare a b of
    LT -> Max b ys
    EQ -> Max a (mappend xs ys)
    GT -> Max a xs
  mappend NoMax a = a
  mappend a NoMax = a
 
solve :: Int -> [Int] -> [Int]
solve siz xs = do
  m <- [0..siz-1]
  let Max _ (Endo f) = fold $ do 
        n <- [0..siz-1]
        ys <- case compare m n of
          LT -> return $ take (n - m + 1) (drop m xs)
          EQ -> []
          GT -> return $ take (m - n + 1) (drop n xs)
        let (us, vs) = halves ys
        let z = sum vs
        return $ Max (z, -n) (Endo (sum us:))
  f []
 
halves :: [a] -> ([a], [a])
halves (x:y:ys) = (x : ls, y : rs) where
  (ls, rs) = halves ys
halves xs = (xs, [])
 
main = do
  siz <- readLn
  xs <- map read <$> words <$> getLine
  print $ maximum $ solve siz xs

提出情報

ジャッジ結果