module Problem150 where

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as W
import Data.List
import Data.Tuple

n :: Int
n = 1000

(!) = (V.!)
(@!) = (W.!)

n2 :: Int
n2 = n * (n + 1) `div` 2

s :: W.Vector Int
s = W.fromList $ snd $ mapAccumL
    (\t _ -> let t' = (615949 * t + 797807) `mod` (2 ^ 20) in (t', t' - (2 ^ 19)))
    0
    [1 .. n2]


triangle :: V.Vector (W.Vector Int)
triangle =
    V.fromList $ (W.singleton 0 :) $ map (W.fromList . scanl (+) 0) $ snd $ mapAccumL
        (\vals n -> swap $ splitAt n vals)
        (map (s @!) [0 .. n2 - 1])
        [1 .. n]

sums :: V.Vector (V.Vector (W.Vector Int))
sums = V.fromList
    [ V.fromList
        [ W.fromList
            [ (triangle ! row @! end)
              - (triangle ! row @! (start - 1))
              + (if row >= 2 && end - start >= 1
                    then sums ! (row - 2) ! (start - 1) @! (end - start - 1)
                    else 0
                )
            | end <- [start .. row]
            ]
        | start <- [1 .. row]
        ]
    | row <- [1 .. n]
    ]

main :: IO ()
main = print $ minimum $ minimum . (W.minimum <$>) <$> sums
