[ZJ] b061: 6. 糊塗情報員

#include<stdio.h>
#include<string.h>
char s[1000];
int v[1000][1000];
long long int dp1[1000][1000],dp2[1000][1000];
void cnt(int l,int r){
    //printf("%d.%d\n",l,r);
    if(v[l][r]) return;
    v[l][r]=1;
    int flag=0,x=0,i;
    long long int maxx=999999999999LL,minn=999999999999LL;
    maxx*=-1;
    for(i=l;i<=r;i++){
        if(s[i]=='*'){
            cnt(l,i-1),cnt(i+1,r);
            //1
            if(dp1[l][i-1]*dp1[i+1][r]>maxx) maxx=dp1[l][i-1]*dp1[i+1][r];
            if(dp1[l][i-1]*dp2[i+1][r]>maxx) maxx=dp1[l][i-1]*dp2[i+1][r];
            if(dp2[l][i-1]*dp1[i+1][r]>maxx) maxx=dp2[l][i-1]*dp1[i+1][r];
            if(dp2[l][i-1]*dp2[i+1][r]>maxx) maxx=dp2[l][i-1]*dp2[i+1][r];
            //2
            if(dp1[l][i-1]*dp1[i+1][r]<minn) minn=dp1[l][i-1]*dp1[i+1][r];
            if(dp1[l][i-1]*dp2[i+1][r]<minn) minn=dp1[l][i-1]*dp2[i+1][r];
            if(dp2[l][i-1]*dp1[i+1][r]<minn) minn=dp2[l][i-1]*dp1[i+1][r];
            if(dp2[l][i-1]*dp2[i+1][r]<minn) minn=dp2[l][i-1]*dp2[i+1][r];
            flag=1;
        }
        if(s[i]=='+'){
            cnt(l,i-1),cnt(i+1,r);
            //1
            if(dp1[l][i-1]+dp1[i+1][r]>maxx) maxx=dp1[l][i-1]+dp1[i+1][r];
            if(dp1[l][i-1]+dp2[i+1][r]>maxx) maxx=dp1[l][i-1]+dp2[i+1][r];
            if(dp2[l][i-1]+dp1[i+1][r]>maxx) maxx=dp2[l][i-1]+dp1[i+1][r];
            if(dp2[l][i-1]+dp2[i+1][r]>maxx) maxx=dp2[l][i-1]+dp2[i+1][r];
            //2
            if(dp1[l][i-1]+dp1[i+1][r]<minn) minn=dp1[l][i-1]+dp1[i+1][r];
            if(dp1[l][i-1]+dp2[i+1][r]<minn) minn=dp1[l][i-1]+dp2[i+1][r];
            if(dp2[l][i-1]+dp1[i+1][r]<minn) minn=dp2[l][i-1]+dp1[i+1][r];
            if(dp2[l][i-1]+dp2[i+1][r]<minn) minn=dp2[l][i-1]+dp2[i+1][r];
            flag=1;
        }
        if(s[i]=='-'){
            cnt(l,i-1),cnt(i+1,r);
            //1
            if(dp1[l][i-1]-dp1[i+1][r]>maxx) maxx=dp1[l][i-1]-dp1[i+1][r];
            if(dp1[l][i-1]-dp2[i+1][r]>maxx) maxx=dp1[l][i-1]-dp2[i+1][r];
            if(dp2[l][i-1]-dp1[i+1][r]>maxx) maxx=dp2[l][i-1]-dp1[i+1][r];
            if(dp2[l][i-1]-dp2[i+1][r]>maxx) maxx=dp2[l][i-1]-dp2[i+1][r];
            //2
            if(dp1[l][i-1]-dp1[i+1][r]<minn) minn=dp1[l][i-1]-dp1[i+1][r];
            if(dp1[l][i-1]-dp2[i+1][r]<minn) minn=dp1[l][i-1]-dp2[i+1][r];
            if(dp2[l][i-1]-dp1[i+1][r]<minn) minn=dp2[l][i-1]-dp1[i+1][r];
            if(dp2[l][i-1]-dp2[i+1][r]<minn) minn=dp2[l][i-1]-dp2[i+1][r];
            flag=1;
        }
    }
    if(flag){
        dp1[l][r]=maxx;
        dp2[l][r]=minn;
    }
    else{
        sscanf(&s[l],"%d",&x);
        dp1[l][r]=x;
        dp2[l][r]=x;
    }
}
int main(){
    int len;
    while(scanf("%s",s)!=EOF){
        memset(v,0,sizeof(v));
        len=strlen(s);
        cnt(0,len-1);
        printf("%lld\n",dp1[0][len-1]);
    }
}