1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <iostream>
#include <cassert>
#include <string>
#include <vector>
#include <limits>
using std::vector;
using std::string;
using std::max;
using std::min;
long long eval(long long a, long long b, char op)
{
if (op == '*') {
return a * b;
} else if (op == '+') {
return a + b;
} else if (op == '-') {
return a - b;
} else {
assert(0);
}
}
void get_min_max(int n, int x, int i, int j, const string &ops, long long *mins, long long *maxs)
{
long long min = std::numeric_limits<long long>::max();
long long max = std::numeric_limits<long long>::min();
for (int k = i; k < j; k++) {
int x = i * n + k;
int y = (k + 1) * n + j;
long long a = eval(maxs[x], maxs[y], ops[k]);
long long b = eval(maxs[x], mins[y], ops[k]);
long long c = eval(mins[x], mins[y], ops[k]);
long long d = eval(mins[x], maxs[y], ops[k]);
if (a < min) min = a;
if (b < min) min = b;
if (c < min) min = c;
if (d < min) min = d;
if (a > max) max = a;
if (b > max) max = b;
if (c > max) max = c;
if (d > max) max = d;
}
mins[x] = min;
maxs[x] = max;
}
long long get_maximum_value(const string &exp)
{
int n = (exp.length() + 1) / 2;
int nn = (n * n);
string ops;
long long *mins = new long long[nn];
long long *maxs = new long long[nn];
// collect the operators
for (int i = 1; i < exp.length(); i+=2)
ops += exp[i];
// feed both diagonals with operands
for (int i = 0, k = 0; i < nn; i+=(n + 1), k+=2)
maxs[i] = mins[i] = (exp[k] - '0');
// feed both first diagonals, result of pair
for (int i = 1, k = 1; i < nn; i+=(n + 1), k+=2)
maxs[i] = mins[i] = eval(mins[i - 1], mins[i + n], exp[k]);
for (int i = 2, k = (n - 2); i < n; i++, k-=1) {
for (int j = 0; j < k; j++) {
int x = i + j * (n + 1);
/* maxs[x] = mins[x] = k; */
/* std::cout << "[" << j <<";"<< j + i<<"]"<< std::endl; */
get_min_max(n, x, j, j + i, ops, mins, maxs);
}
}
/* std::cout << std::endl; */
/* for (int i = 0; i < nn; i+=n) { */
/* for (int j = 0; j < n; j++) */
/* std::cout << mins[i + j] << " "; */
/* std::cout << std::endl; */
/* } */
/* std::cout << std::endl; */
/* for (int i = 0; i < nn; i+=n) { */
/* for (int j = 0; j < n; j++) */
/* std::cout << maxs[i + j] << " "; */
/* std::cout << std::endl; */
/* } */
/* std::cout << std::endl; */
long long ret = maxs[n - 1];
delete [] mins;
delete [] maxs;
return ret;
}
int main() {
string s;
std::cin >> s;
std::cout << get_maximum_value(s) << '\n';
}
|
