Submission 826 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
826	15/05/2013 22:48:26	leandro	A - Jornada	Accepted	16	1.2 KiB	GNU G++ 5.1.0

Code

/*
    username: leandro
	program: Jornada
	lang: C++
*/

#include <cstdio>
#include <algorithm>

using namespace std;

const int
      MaxN = 2010;

int N, i, j;
char s[MaxN];
bool mark[2][MaxN];
int dp_min[2][MaxN];
int dp_max[2][MaxN];

void ini(int x) {
    for (j = 1; j <= N; j++) {
	    dp_min[x % 2][j] = MaxN;
		dp_max[x % 2][j] =    0;
		mark[x % 2][j] = false;
	}
}

void calc(int x, int add) {
    for (j = 1; j <= N; j++)
	    if (mark[1 - (x % 2)][j + add]) {
		    int val_min = max(dp_min[1 - (x % 2)][j + add], j - 1);
			int val_max = max(dp_max[1 - (x % 2)][j + add], j - 1);
			dp_min[x % 2][j] = min(dp_min[x % 2][j], val_min);
			dp_max[x % 2][j] = max(dp_max[x % 2][j], val_max);
			mark[x % 2][j] = true;
	    }
}

int main() {
    
	scanf("%d", &N);
	scanf("%s", s + 1);
	
	mark[0][1] = true;
	for (i = 1; i <= N; i++) {
	    ini(i);
		if (s[i] == '-' || s[i] == '?') calc(i, +1);
		if (s[i] == '+' || s[i] == '?') calc(i, -1);
	}

printf("%d %d\n", dp_min[N % 2][1], dp_max[N % 2][1]);
	
    return 0;
}

Judgement Details

Test 01: 0.023 0.000 1220K ok
Test 02: 0.009 0.000 1220K ok
Test 03: 0.010 0.000 1220K ok
Test 04: 0.010 0.000 1216K ok
Test 05: 0.012 0.016 1220K ok
Test 06: 0.009 0.000 1216K ok
Test 07: 0.010 0.000 1220K ok
Test 08: 0.010 0.000 1216K ok
Test 09: 0.014 0.016 1264K ok
Test 10: 0.021 0.016 1264K ok
Test 11: 0.028 0.016 1236K ok
Test 12: 0.009 0.000 1216K ok
Test 13: 0.027 0.016 1232K ok
Test 14: 0.009 0.000 1220K ok
Test 15: 0.009 0.000 1220K ok
Test 16: 0.009 0.000 1216K ok
Test 17: 0.009 0.000 1216K ok
Test 18: 0.009 0.000 1248K ok
Test 19: 0.008 0.000 1220K ok
Test 20: 0.009 0.000 1220K ok
Accepted

Matcom Online Grader