arithmetic.cpp

#include <cstdio>
#include <vector>
#include <string>
#include <climits>
#include <tuple>
#include <cstring>

using namespace std;

struct Expression
{
    string* arr;
    int begin;
    int end;

    tuple<Expression, Expression> subexp(int op_index) const
    {
        return make_tuple<Expression, Expression>(
            Expression{ arr, begin, op_index - 1 },
            Expression{ arr, op_index + 1, end });
    }
};

static int(*max_cache)[201][201];
static bool(*max_cache_flag)[201][201];
static int(*min_cache)[201][201];
static bool(*min_cache_flag)[201][201];

int get_min(Expression exp);

int get_max(Expression exp)
{
    if (exp.begin == exp.end)
        return stoi(exp.arr[exp.begin]);

    if ((*max_cache_flag)[exp.begin][exp.end])
        return (*max_cache)[exp.begin][exp.end];

    int max_result = INT_MIN;

    for (int op_index = exp.begin + 1; op_index < exp.end; op_index += 2)
    {
        auto& op = exp.arr[op_index];
        Expression left_side_exp;
        Expression right_side_exp;
        tie(left_side_exp, right_side_exp) = exp.subexp(op_index);
        if (op == "+")
        {
            int result = get_max(left_side_exp) + get_max(right_side_exp);
            if (result > max_result)
                max_result = result;
        }
        else if (op == "-")
        {
            int result = get_max(left_side_exp) - get_min(right_side_exp);
            if (result > max_result)
                max_result = result;
        }
        else
        {
            printf("ASSERT! op is neither + nor -\n");
        }
    }

    (*max_cache_flag)[exp.begin][exp.end] = true;
    (*max_cache)[exp.begin][exp.end] = max_result;

    return max_result;
}

int get_min(Expression exp)
{
    if (exp.begin == exp.end)
        return stoi(exp.arr[exp.begin]);

    if ((*min_cache_flag)[exp.begin][exp.end])
        return (*min_cache)[exp.begin][exp.end];

    int min_result = INT_MAX;

    for (int op_index = exp.begin + 1; op_index < exp.end; op_index += 2)
    {
        auto& op = exp.arr[op_index];
        Expression left_side_exp;
        Expression right_side_exp;
        tie(left_side_exp, right_side_exp) = exp.subexp(op_index);
        if (op == "+")
        {
            int result = get_min(left_side_exp) + get_min(right_side_exp);
            if (result < min_result)
                min_result = result;
        }
        else if (op == "-")
        {
            int result = get_min(left_side_exp) - get_max(right_side_exp);
            if (result < min_result)
                min_result = result;
        }
        else
        {
            printf("ASSERT! op is neither + nor -\n");
        }
    }

    (*min_cache_flag)[exp.begin][exp.end] = true;
    (*min_cache)[exp.begin][exp.end] = min_result;

    return min_result;
}

int solution(vector<string> arr)
{
    max_cache = static_cast<decltype(max_cache)>(malloc(sizeof(*max_cache)));
    max_cache_flag = static_cast<decltype(max_cache_flag)>(malloc(sizeof(*max_cache_flag)));
    min_cache = static_cast<decltype(min_cache)>(malloc(sizeof(*min_cache)));
    min_cache_flag = static_cast<decltype(min_cache_flag)>(malloc(sizeof(*min_cache)));
    memset(*max_cache_flag, 0, sizeof(*max_cache_flag));
    memset(*min_cache_flag, 0, sizeof(*min_cache_flag));
    Expression exp{ arr.data(), 0, (int)arr.size() - 1 };
    int result = get_max(exp);
    free(max_cache);
    free(max_cache_flag);
    free(min_cache);
    free(min_cache_flag);
    return result;
}