私の解答を公開します
全ケース(おまけ付き)をまとめて0.01sくらいで求めることが出来ます
http://ideone.com/dYyECD C++ 解説付き
http://ideone.com/PjeGIW Haskell

この問題は間違ったアルゴリズムでも正解に近い値を出せてしまい、バグがあってもわかりづらくなっています
どうやってプログラムの正当性を確認しようかと悩んだのですが、テストケースを増やすことしか思いつきませんでした
というわけで以下のケースをおまけとして実行してみました
__258___3_9________5__7__4__9______ > 99