Submission #1177983
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 dp[100000][3];
int func(int n, int o) //括弧がo個開いている時、n番目以降を使ってつくれる最大の数
{
if (dp[n][o] < INIT)
{
return dp[n][o];
}
int res;
if (n == N - 1)
{
if (o % 2 == 0)
{
res = A[n];
}
else
{
res = -A[n];
}
}
else
{
if (op[n + 1] == '+')
{
if (o == 0)
{
res = A[n] + func(n, o);
}
else if (o == 1)
{
int d1 = -A[n] + func(n + 1, o);
int d2 = -A[n] + func(n + 1, o - 1);
res = MAX(d1, d2);
}
else if (o == 2)
{
int d1 = A[n] + func(n + 1, o);
int d2 = A[n] + func(n + 1, o - 1);
int d3 = A[n] + func(n + 1, o - 2);
res = MAX(d1, MAX(d2, d3));
}
}
else
{
if (o == 0)
{
res = A[n] + func(n + 1, o + 1);
}
else if (o == 1)
{
int d1 = -A[n] + func(n + 1, o + 1);
int d2 = -A[n] + func(n + 1, o);
res = MAX(d1, d2);
}
else if (o == 2)
{
int d1 = A[n] + func(n + 1, o);
int d2 = A[n] + func(n + 1, o - 1);
res = MAX(d1, d2);
}
}
}
dp[n][o] = res;
return res;
}
signed main()
{
cin >> N;
op[0] = '+';
for (int i = 0; i < N; i++)
{
if (i > 0)
{
cin >> op[i];
}
cin >> A[i];
for (int j = 0; j < 3; j++) dp[i][j] = INIT;
}
cout << func(0, 0) << endl;
}
Submission Info
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_alladd_01.txt, subtask_1_alladd_02.txt, subtask_1_alladd_03.txt, subtask_1_alladd_04.txt, subtask_1_allsub_01.txt, subtask_1_allsub_02.txt, subtask_1_allsub_03.txt, subtask_1_allsub_04.txt, subtask_1_cont_01.txt, subtask_1_cont_02.txt, subtask_1_cont_03.txt, subtask_1_cont_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_killer_03.txt, subtask_1_killer_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_max_03.txt, subtask_1_max_04.txt, subtask_1_min_01.txt, subtask_1_min_02.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt, subtask_1_rand_04.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_alladd_01.txt |
RE |
262 ms |
265600 KB |
subtask_1_alladd_02.txt |
RE |
262 ms |
265600 KB |
subtask_1_alladd_03.txt |
RE |
264 ms |
265600 KB |
subtask_1_alladd_04.txt |
RE |
262 ms |
265600 KB |
subtask_1_allsub_01.txt |
AC |
54 ms |
9728 KB |
subtask_1_allsub_02.txt |
AC |
54 ms |
9728 KB |
subtask_1_allsub_03.txt |
AC |
54 ms |
9728 KB |
subtask_1_allsub_04.txt |
AC |
56 ms |
9728 KB |
subtask_1_cont_01.txt |
RE |
240 ms |
264064 KB |
subtask_1_cont_02.txt |
RE |
234 ms |
263680 KB |
subtask_1_cont_03.txt |
RE |
231 ms |
263424 KB |
subtask_1_cont_04.txt |
RE |
219 ms |
262656 KB |
subtask_1_killer_01.txt |
RE |
260 ms |
267392 KB |
subtask_1_killer_02.txt |
RE |
245 ms |
264448 KB |
subtask_1_killer_03.txt |
RE |
260 ms |
265472 KB |
subtask_1_killer_04.txt |
RE |
246 ms |
264448 KB |
subtask_1_max_01.txt |
RE |
262 ms |
265600 KB |
subtask_1_max_02.txt |
RE |
262 ms |
265600 KB |
subtask_1_max_03.txt |
RE |
263 ms |
265600 KB |
subtask_1_max_04.txt |
RE |
264 ms |
265600 KB |
subtask_1_min_01.txt |
AC |
1 ms |
256 KB |
subtask_1_min_02.txt |
AC |
1 ms |
256 KB |
subtask_1_rand_01.txt |
RE |
245 ms |
264320 KB |
subtask_1_rand_02.txt |
RE |
251 ms |
264704 KB |
subtask_1_rand_03.txt |
RE |
218 ms |
262656 KB |
subtask_1_rand_04.txt |
RE |
232 ms |
263296 KB |