SMMR-T158: Quick Maths

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

enum status {
    MIN, MAX
};

const int N = 500;

int arr[N + 1];
char opr[N + 1];
lli dp[N + 1][N + 1][2];

int main(){

    int nArr;
    scanf("%d", &nArr);
    for(int i = 1; i < nArr; ++i){
        scanf("%d %c", &arr[i], &opr[i]);
    }
    scanf("%d", &arr[nArr]);
    for(int i = 1; i <= nArr; ++i){
        dp[i][i][MIN] = arr[i];
        dp[i][i][MAX] = arr[i];
    }
    for(int d = 2; d <= nArr; ++d){
        for(int l = 1; l <= nArr - d + 1; ++l){
            int r = l + d - 1;
            lli ansMax = -1e18;
            lli ansMin = 1e18;
            for(int i = l; i < r; ++i){
                if(opr[i] == '+'){
                    ansMax = max(ansMax, dp[l][i][MAX] + dp[i + 1][r][MAX]);
                    ansMin = min(ansMin, dp[l][i][MIN] + dp[i + 1][r][MIN]);
                } else if(opr[i] == '-'){
                    ansMax = max(ansMax, dp[l][i][MAX] - dp[i + 1][r][MIN]);
                    ansMin = min(ansMin, dp[l][i][MIN] - dp[i + 1][r][MAX]);
                }
            }
            dp[l][r][MAX] = ansMax;
            dp[l][r][MIN] = ansMin;
        }
    }
    cout << dp[1][nArr][MIN] << ' ' << dp[1][nArr][MAX];

    return 0;
}