UVa 11258 String Partition Solution

s=""
dp=[None]
def rec(prev,sum,i):
    global s,dp
    if i==len(s):
        return int(prev)+sum
    if i>0 and prev==s[i-1] and dp[i-1]:
        return sum+dp[i-1]
    dp[i]=rec(s[i],0,i+1)
    if (10*int(prev)+int(s[i]))>((1<<31)-1):
        return sum+int(prev)+dp[i]
    else:
        return max(rec(prev+s[i],sum,i+1),sum+int(prev)+dp[i])
def Main():
    t=int(input())
    while t>0:
        t-=1
        global s,dp
        s=input()
        dp=[None for x in range(len(s))]
        print(rec("0",0,0))
if __name__=="__main__":
    Main()