【39.29%】【codeforces 552E】Vanya and Brackets

时间:2023-03-09 14:26:43
【39.29%】【codeforces 552E】Vanya and Brackets

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

Vanya is doing his maths homework. He has an expression of form , where x1, x2, …, xn 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.

Examples

input

3+5*7+8*4

output

303

input

2+3*5

output

25

input

3*4*5

output

60

Note

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).

【题目链接】:http://codeforces.com/contest/552/problem/E

【题解】



括号肯定要加在乘号的旁边,或者加在最开头或最结尾这样最好.

不然你加在加号的旁边没有意义的。。

因为乘号最多15个再加上开头和结尾。总共17个;

就O(17^2*长度);

枚举括号的C(N,2)个组合,然后写个函数搞出表达式的值就好.



【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x) typedef pair<int,int> pii;
typedef pair<LL,LL> pll; //const int MAXN = x;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0); string s;
vector <int> a;
stack <char> ch;
stack <LL> num; LL cl2(LL x,LL y,char key)
{
if (key=='+') return x+y;
else
return x*y;
} void cal()
{
LL x = num.top();
num.pop();
LL y = num.top();
num.pop();
LL z = cl2(x,y,ch.top());
ch.pop();
num.push(z);
} LL cl(string s)
{
int len = s.size();
rep1(i,0,len-1)
if (s[i] == '(')
ch.push(s[i]);
else
if (isdigit(s[i]))
num.push(s[i]-'0');
else
if (s[i]=='*')
ch.push(s[i]);
else
if (s[i]=='+')
{
while (!ch.empty() &&ch.top()=='*')
cal();
ch.push(s[i]);
}
else
if (s[i]==')')
{
while (ch.top()!='(')
cal();
ch.pop();
}
while (!ch.empty())
cal();
return num.top();
} int main()
{
//freopen("F:\\rush.txt","r",stdin);
cin >> s;
a.pb(-1);
int len = s.size();
for (int i = 1;i <= len-1;i+=2)
if (s[i]=='*')
a.pb(i);
a.pb(len);
LL ans = 0;
len = a.size();
rep1(i,0,len-2)
rep1(j,i+1,len-1)
{
int l = a[i],r = a[j];
string temps = s;
temps.insert(l+1,"(");
temps.insert(r+1,")");
while (!num.empty()) num.pop();
ans = max(ans,cl(temps));
}
cout << ans << endl;
return 0;
}