Submission #1177661

---

Source Code Expand

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#define int long long
#define uint unsigned long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
using namespace std;

int INIT = 1000000000000000L; //10^5 * 10^9 * 10

int N;
int A[100000];
char op[100000];

int max_dp[100000];
int min_dp[100000];

int get_max(int n);
int get_min(int n);

int get_max(int n) //n以降を作って作れるで最大の数
{
	if (n == N - 1)
	{
		return A[n];
	}

	if (max_dp[n] < INIT)
	{
		return max_dp[n];
	}

	int res;
	if (n == 0 || op[n - 1] == '+')
 	{
		res = A[n] + get_max(n + 1);
	}
	else
	{
		int d1 = -A[n] + get_max(n + 1);
		int d2 = -(A[n] + get_max(n + 1));
		int d3 = -A[n] + get_min(n + 1);
		int d4 = -(A[n] + get_min(n + 1));
		if (d1 >= d2 && d1 >= d3 && d1 >= d4)
		{
			res = d1;
		}
		else if (d2 >= d1 && d2 >= d3 && d2 >= d4)
		{
			res = d2;
		}
		else if (d3 >= d1 && d3 >= d2 && d3 >= d4)
		{
			res = d3;
		}
		else if (d4 >= d1 && d4 >= d2 && d4 >= d3)
		{
			res = d4;
		}
	}
	max_dp[n] = res;
	return res;
}

int get_min(int n) //n以降を作って作れるで最小の数
{
	if (n == N - 1)
	{
		return A[n];
	}

	if (min_dp[n] < INIT)
	{
		return min_dp[n];
	}

	int res;
	if (n == 0 || op[n - 1] == '+')
	{
		res = A[n] + get_min(n + 1);
	}
	else
	{
		int d1 = -A[n] + get_max(n + 1);
		int d2 = -(A[n] + get_max(n + 1));
		int d3 = -A[n] + get_min(n + 1);
		int d4 = -(A[n] + get_min(n + 1));
		if (d1 <= d2 && d1 <= d3 && d1 <= d4)
		{
			res = d1;
		}
		else if (d2 <= d1 && d2 <= d3 && d2 <= d4)
		{
			res = d2;
		}
		else if (d3 <= d1 && d3 <= d2 && d3 <= d4)
		{
			res = d3;
		}
		else if (d4 <= d1 && d4 <= d2 && d4 <= d3)
		{
			res = d4;
		}
	}
	min_dp[n] = res;
	return res;
}

signed main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		if (i < N - 1) cin >> op[i];
	}
	for (int i = 0; i < N; i++)
	{
		max_dp[i] = INIT;
		min_dp[i] = INIT;
	}
	cout << get_max(0) << endl;
}

Submission Info

Judge Result