SPOJ の時間制限が厳しい件について

Lost Dog さんの記事が面白そうだったのと、あなごるのサーバが落ちてて何もできなかったのとで、SPOJ に初挑戦。
https://www.spoj.pl/problems/TRT/
問題は Problem 67 - Project Euler に近いと思います。O(n²) の DP（？）で解きました。
ただ、何も工夫しないと 1s で終わらず TLE になってしまうので、

1. インデックスアクセスしてるところはリストから配列に
2. 正格評価を使う
3. foldl' とか zipWith とか使ってたのをやめてベタに再帰

などで高速化を図りました。
なんとか accept されましたが、もうちょいスマートな解き方がないもんでしょうか？
以下にソースコードを載せておきます。可読性は著しく低いので、ネタバレにはならないかと。

import Data.Array

main = interact $ show . trt . map read . lines

trt (n:vs) = f (n-1) $ map (*n) $ take n vs where
  as = listArray (0,n-1) vs
  f 0 [m] = m
  f d ms = f (d-1) $ g 0 ms where
    g i (m1:m2:ms) = seq m' $ m' : g (i+1) (m2:ms) where
      m' = max (m1+d*as!(n-d+i)) (m2+d*as!i)
    g _ _ = []