The correct, optimal and working solution for programming question LISA on spoj

#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <limits> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <utility> #include <vector> #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define REP(I,N) FOR(I,0,N) #define ALL(A) (A).begin(), (A).end() using namespace std; int main(){ int n; cin >> n; while(n--){ string tmp; cin >> tmp; vector<int> numbers; vector<char> operators; FOR(i, 0, tmp.size()){ if(i % 2 == 0){ numbers.push_back(atoi(&tmp[i])); } else { operators.push_back(tmp[i]); } } vector< vector<long long> > min_costs(numbers.size() + 1, vector<long long>(numbers.size() + 1, numeric_limits<int>::max())); vector< vector<long long> > max_costs(numbers.size() + 1, vector<long long>(numbers.size() + 1, 0)); FOR(i, 0, numbers.size() + 1){ max_costs[i][i] = min_costs[i][i] = numbers[i]; } int numbers_total = numbers.size(); FOR(l, 2, numbers_total + 1){ FOR(i, 0, numbers_total - l + 1){ int j = i + l - 1; FOR(k, i, j){ int min_tmp = 0; int max_tmp = 0; if(operators[k] == '+'){ min_tmp = min_costs[i][k] + min_costs[k+1][j]; max_tmp = max_costs[i][k] + max_costs[k+1][j]; }else if(operators[k] == '*'){ min_tmp = min_costs[i][k] * min_costs[k+1][j]; max_tmp = max_costs[i][k] * max_costs[k+1][j]; } if(min_tmp < min_costs[i][j]){ min_costs[i][j] = min_tmp; } if(max_tmp > max_costs[i][j]){ max_costs[i][j] = max_tmp; } } } } cout << max_costs[0][numbers_total-1] << " " << min_costs[0][numbers_total-1] << endl; } }