Как эта замещенная таблица DP слишком медленная для SPOJ?

SPOILERS: Я работаю над http://www.spoj.pl/problems/KNAPSACK/, поэтому не заглядывайте, если вы не хотите, чтобы возможное решение испортилось для вас.

Шаблон:

import Data.Sequence (index, fromList)
import Data.MemoCombinators (memo2, integral)

main = interact knapsackStr

knapsackStr :: String -> String
knapsackStr str = show $ knapsack items capacity numItems
  where [capacity, numItems] = map read . words $ head ls
        ls = lines str
        items = map (makeItem . words) $ take numItems $ tail ls

Некоторые типы и помощники для установки сцены:

type Item = (Weight, Value)
type Weight = Int
type Value = Int

weight :: Item -> Weight
weight = fst

value :: Item -> Value
value = snd

makeItem :: [String] -> Item
makeItem [w, v] = (read w, read v)

И основная функция:

knapsack :: [Item] -> Weight -> Int -> Value
knapsack itemsList = go
  where go = memo2 integral integral knapsack'
        items = fromList $ (0,0):itemsList
        knapsack' 0 _ = 0
        knapsack' _ 0 = 0
        knapsack' w i | wi > w    = exclude
                      | otherwise = max exclude include
          where wi = weight item
                vi = value item
                item = items `index` i
                exclude = go w (i-1)
                include = go (w-wi) (i-1) + vi

И этот код работает; Я попытался подключить тестовый пример SPOJ, и он дает правильный результат. Но когда я отправляю это решение на SPOJ (вместо импорта MemoCombinators от Luke Palmer, я просто копирую и вставляю необходимые части в отправленный источник), он превышает срок. =/

Я не понимаю, почему; Я спросил ранее об эффективном способе выполнения рюкзака 0-1, и я уверен, что это примерно так же быстро, как и получается: memoized функция, которая будет только рекурсивно вычислять подзаголовки, которые ему абсолютно необходимы, чтобы получить правильный результат. Я каким-то образом испортил мемуары? Есть ли медленный момент в этом коде, который мне не хватает? SPOJ просто предвзято относится к Haskell?

Я даже положил {-# OPTIONS_GHC -O2 #-} в начало представления, но, увы, это не помогло. Я пробовал аналогичное решение, которое использует 2D-массив Sequence s, но также отклонялся как слишком медленный.

Ответы

integral :: Memo Int
integral = wrap id id bits