[Haskell-beginners] How to improve performace of a dfs program

[xiong.hua]

hi ,all :

   I'm a learn haskell couple of days , and I want to solve some problem
[http://codeforces.com/contest/194/problem/D] with haskell , I know the
algorithm for the problem and implement it with haskell , but i jsut get TLE
on the test case . Here is my code , how i can implement it more Efficient ?

 

code : 

import Data.Bits

import Data.Int

--import Debug.Trace

 

calc :: [Int64] -> [Int64] -> Int64

calc a b = sum $ zipWith (*) a b

 

 

-- a p r

fun2op :: [Int64] -> [Int] -> Int64 -> [Int64]

--fun2op a x r |

--   trace ("fun2op " ++ show a ++ " " ++ show x ++ " " ++ show r ) False =
undefined

fun2op _ [] _ = []

fun2op a (x:xs) r = (( a !! (x-1)) + r) : (fun2op a xs r )

 

gor :: [Int64] -> [Int64] -> Int -> Int -> Int64 -> Int64

gor a k dep u ans

         | (  ( u - dep ) .&.  1 :: Int) == 0 = max ans $ calc a k

         | otherwise = ans   

 

-- a , b , p , k  , r , u , last , dep , ans

dfs :: [Int64] -> [Int64] -> [Int] -> [Int64] -> Int64 -> Int -> Int -> Int
-> Int64 -> Int64

 

dfs a b p k r u l dep ans

--    | trace ("dfs " ++ show a ++ " " ++ show l ++ " " ++  show dep ++ " "
++ show ans) False = undefined

    | dep == u = max ans $ calc a k 

    | l == 1  = df1

    | otherwise  = max (df1) ( dfs (zipWith ( xor ) a b ) b p k r u 1
(dep+1) tmpans)

    where

        pa = fun2op a p r

        tmpans = gor a k dep u ans

        df1 = dfs pa b p k r u 2 (dep + 1) tmpans

 

 

rInt64 :: String -> Int64

rInt64 = read

 

rInt :: String -> Int

rInt = read

 

main = do

    ss <- getLine

    let tmp = words ss

    let u = rInt (tmp !! 1)

    let r = rInt64 ( tmp !! 2)

    let x = map (rInt) $ words ss

    let x = map (rInt) $ words ss

    aa <- getLine

    let a = map (rInt64) $ words aa

    bb <- getLine

    let b = map (rInt64) $ words bb

    kk <- getLine

    let k = map (rInt64) $ words kk

    pp <- getLine

    let p = map (rInt) $ words pp

    print ( dfs a b p k r u 0 0 (rInt64 "-1000000000000000000"))

 

--------------

Best Regards

GTALK: ivoryxiong AT gmail.com

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120605/d4f6dd8a/attachment-0001.htm>