import Data.Bool import Data.IntMap.Strict ((!)) import qualified Data.IntMap.Strict as M import qualified Data.Set as S type Vertex = Int type Cost = Int type Heap = S.Set (Cost, Vertex) nullq = S.null empty = S.empty push v c = S.insert (c,v) pop = S.deleteFindMax modulo = 1000 pos x y = modulo*x + y north p = p - modulo south p = p + modulo east p = succ p west p = pred p main = do [n,v,ox,oy] <- map read . words <$> getLine ls <- map read . words <$> getContents putStrLn (bool "NO" "YES" (oasys n v ox oy ls)) oasys n v ox oy ls = M.member pds im1 || ((M.member po im1) && (M.member pds im2)) where (im1,_) = until (nullq . snd) (dp g) (im0,q0) (im2,_) = until (nullq . snd) (dp g) (im0,q1) pdp = pos 1 1 pds = pos n n po = pos oy ox g = M.fromDistinctAscList (zip [pos x y | x<-[1..n], y<-[1..n]] ls) im0 = M.empty q0 = push pdp v empty q1 = push po ((im1!po)*2) empty dp g (im,q) | h < 1 = (im,q') | M.member v im = (im,q') | otherwise = (im',q'') where ((h,v),q') = pop q im' = M.insertWith max v h im q'' = foldr (\w acc -> push w (h-(g!w)) acc) q' vns vns = filter (\w -> M.member w g) (sequence [north,south,east,west] v)