CodeForces - 552E Vanya and Brackets

Vanya and Brackets

Time Limit: 1000MS

Memory Limit: 262144KB

64bit IO Format: %I64d & %I64u

Description

Vanya is doing his maths homework. He has an expression of form , where x₁, x₂, ..., x_n are digits from 1 to 9, and sign represents either a plus '+' or the multiplication sign '*'. Vanya needs to add one pair of brackets in this expression so that to maximize the value of the resulting expression.

Input

The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs + and * .

The number of signs * doesn't exceed 15.

Output

In the first line print the maximum possible value of an expression.

Sample Input

Input

3+5*7+8*4

Output

Input

2+3*5

Output

Input

3*4*5

Output

Hint

Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.

Note to the second sample test. (2 + 3) * 5 = 25.

Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).

Source

Codeforces Round #308 (Div. 2)

解题：暴力瞎搞，注意int溢出，傻逼逼的把栈写成int了。。。哎吸取教训

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 vector<int>pos;

 stack<LL>num;

 stack<char>op;

 LL calc(const string &str) {

     while(!num.empty()) num.pop();

     while(!op.empty()) op.pop();

     for(int i = ,slen = str.length(); i < slen; ++i) {

         if(str[i] == ')') {

             while(op.top() != '(') {

                 LL tmp = num.top();

                 num.pop();

                 if(op.top() == '*') num.top() *= tmp;

                 else if(op.top() == '+') num.top() += tmp;

                 op.pop();

             }

             op.pop();

             continue;

         }

         if(isdigit(str[i])) num.push(str[i] - '');

         else if(str[i] == '+' && !op.empty() && op.top() == '*') {

             while(!op.empty() && op.top() == '*') {

                 LL tmp = num.top();

                 num.pop();

                 num.top() *= tmp;

                 op.pop();

             }

             op.push(str[i]);

         } else op.push(str[i]);

     }

     while(!op.empty()) {

         LL tmp = num.top();

         num.pop();

         if(op.top() == '*') num.top() *= tmp;

         else if(op.top() == '+') num.top() += tmp;

         op.pop();

     }

     return num.top();

 }

 int main() {

     string str;

     cin>>str;

     pos.push_back(-);

     int slen = str.length();

     for(int i = ; i < slen; i += )

         if(str[i] == '*') pos.push_back(i);

     pos.push_back(slen);

     slen = pos.size();

     LL ret = INT_MIN;

     for(int i = ; i+ < slen; ++i)

         for(int j = i+; j < slen; ++j) {

             string s = str;

             s.insert(pos[i]+,,'(');

             s.insert(pos[j]+,,')');

             ret = max(ret,calc(s));

         }

     cout<<ret<<endl;

     return ;

 }

巴特西

CodeForces - 552E Vanya and Brackets

最新文章

热门文章