逆ポーランド記法はスタックを用いてO(N)O(N)O(N)で計算できます.
評価式の初めの位置:lllを固定した時,全部のrrrに対するポーランド記法の総和はその過程でO(N)O(N)O(N)で計算できます.
lllを全探索すればO(N2)O(N^2)O(N2)程度で答えを求めることができます.