逆ポーランド記法はスタックを用いてO(N)O(N)で計算できます.

評価式の初めの位置:llを固定した時,全部のrrに対するポーランド記法の総和はその過程でO(N)O(N)で計算できます.

llを全探索すればO(N2)O(N^2)程度で答えを求めることができます.