Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //https://www.spoj.com/problems/LISA/
- // I can't tell you what it really is,
- // I can only tell you what it feels like.
- #include "bits/stdc++.h"
- using namespace std;
- #define int long long
- auto operator+=(pair<int,int> &x, const pair<int,int> &y) {
- x.first += y.first;
- x.second += y.second;
- return x;
- }
- auto operator*=(pair<int,int> &x, const pair<int,int> &y) {
- x.first *= y.first;
- x.second *= y.second;
- return x;
- }
- auto operator-=(pair<int,int> &x, const pair<int,int> &y) {
- x.first -= y.first;
- x.second -= y.second;
- return x;
- }
- const int N = 102;
- const int inf = numeric_limits<int>::max();
- const int ninf = numeric_limits<int>::min();
- char s[N];
- int a[N];
- pair<int,int> dp[N][N];
- const pair<int,int> ok = make_pair(-1,-1);
- void pre() {
- for (int i = 0; i < N; ++i) {
- for (int j = 0; j < N; ++j) {
- dp[i][j] = ok;
- }
- }
- }
- pair<int,int> go(int l, int r) {
- if (l == r) return make_pair(a[l],a[l]);
- if (dp[l][r] != ok) return dp[l][r];
- int ans = inf;
- pair<int,int> findL, findR;
- int mn = inf, mx = ninf;
- for (int i = l; i < r; ++i) {
- findL = go(l,i);
- findR = go(i+1,r);
- switch(s[i]) {
- case '+':
- findL += findR; break;
- case '*':
- findL *= findR; break;
- case '-':
- findL -= findR; break;
- }
- mn = min(mn, findL.first);
- mx = max(mx ,findL.second);
- }
- return dp[l][r] = make_pair(mn, mx);
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- string str;
- int t = 1; cin >> t;
- while (t--) {
- int n = 0;
- pre();
- cin >> str;
- for (int i = 0; i < str.size(); ++i) {
- if (isdigit(str[i])) a[n++] = str[i] - '0';
- else s[n-1] = str[i];
- }
- auto it = go(0,n-1);
- cout << it.second << ' ' << it.first << '\n';
- }
- return 0;
- }
- // 1). Try forming/rearranging the equations if any
- // 2). If problem asks to count, try counting in reverse(it can be easier sometimes)
Add Comment
Please, Sign In to add comment