結果

問題 No.127 門松もどき
コンテスト
ユーザー tottoripaper
提出日時 2015-05-09 22:27:35
言語 Haskell
(9.10.1)
結果
RE  
実行時間 -
コード長 1,486 bytes
コンパイル時間 10,663 ms
コンパイル使用メモリ 208,768 KB
実行使用メモリ 288,032 KB
最終ジャッジ日時 2024-07-05 21:19:38
合計ジャッジ時間 25,184 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22 RE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

-- [元のコード] http://yukicoder.me/submissions/15723

import Control.Monad
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Debug.Trace
    
readInts :: B.ByteString -> [Int]
readInts = map (fst . fromJust . B.readInt) . B.words

getInts :: IO [Int]
getInts = liftM readInts B.getLine

main = do
  n <- readLn
  as <- liftM V.fromList getInts
  dp <- MV.replicate (2*3000*3000) (-1 :: Int)
  let
      at l r p =  l + 3000 * (r + 3000 * p)
      f :: Int -> Int -> Int -> IO Int
      f l r p
        | l == r = return 0
        | otherwise = do
            v <- MV.read dp (at l r p)
            if v /= (-1)
            then return v
            else g l r p
      g :: Int -> Int -> Int -> IO Int
      g l r p
        | p == 0 = do
            v <- f l (r-1) p
            v' <- if as V.! l < as V.! r then liftM (+1) (f (l+1) r (1-p)) else return 0
            let res = max v v'
            MV.write dp (at l r p) res
            return res
        | otherwise = do
            v <- f (l+1) r p
            v' <- if as V.! r < as V.! l then liftM (+1) (f l (r-1) (1-p)) else return 0
            let res = max v v'
            MV.write dp (at l r p) res
            return res
      xs = liftM concat $ forM [0..n-1] $ \i ->
               forM [i+1..n-1] $ \j ->
                   liftM2 (((+1).) . max) (f i j 0) (f i j 1)
   in print =<< liftM maximum xs
0