제출 #680784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680784		rainboy	Security Gate (JOI18_security_gate)	C11	100 / 100	341 ms	3220 KiB

securitygate

#include <stdio.h>
#include <string.h>

#define N	300
#define MD	1000000007

void flip(char *cc, int n) {
	int i, j;
	char tmp;

	for (i = 0; i < n; i++)
		cc[i] = cc[i] == 'x' ? 'x' : (cc[i] == '(' ? ')' : '(');
	for (i = 0, j = n - 1; i < j; i++, j--)
		tmp = cc[i], cc[i] = cc[j], cc[j] = tmp;
}

int solve1(char *cc, int n) {
	static int dp[N + 1], dq[N + 1];
	int i, d;

	memset(dp, 0, (n + 1) * sizeof *dp), dp[0] = 1;
	for (i = 0; i < n; i++) {
		memset(dq, 0, (n + 1) * sizeof *dq);
		for (d = 0; d <= n; d++) {
			int x = dp[d];

			if (x == 0)
				continue;
			if (cc[i] == '(' || cc[i] == 'x')
				dq[d + 1] = (dq[d + 1] + x) % MD;
			if ((cc[i] == ')' || cc[i] == 'x') && d > 0)
				dq[d - 1] = (dq[d - 1] + x) % MD;
		}
		memcpy(dp, dq, (n + 1) * sizeof *dq);
	}
	return dp[0];
}

int solve2(char *cc, int n) {
	static int dp[N + 1][N + 1], dq[N + 1][N + 1], dq_[N + 1][N + 1], dr[N + 1][N + 1], dr_[N + 1][N + 1];
	int i, d, a, a_, b, b_, ans;

	for (i = 0; i <= n; i++)
		memset(dp[i], 0, (n + 1) * sizeof *dp[i]);
	dp[0][0] = 1;
	for (i = 0; i < n; i++)
		for (d = 0; d <= n; d++) {
			int x = dp[i][d];

			if (x == 0)
				continue;
			if (cc[i] == '(' || cc[i] == 'x')
				dp[i + 1][d + 1] = (dp[i + 1][d + 1] + x) % MD;
			if ((cc[i] == ')' || cc[i] == 'x') && d > 0)
				dp[i + 1][d - 1] = (dp[i + 1][d - 1] + x) % MD;
		}
	for (a = 0; a <= n; a++)
		for (b = 0; b <= a; b++)
			dq[a][b] = dr[a][b] = 0;
	dq[0][0] = 1;
	ans = 0;
	for (i = n - 1; i >= 0; i--) {
		for (a = 0; a <= n; a++)
			for (b = 0; b <= a; b++)
				dq_[a][b] = dr_[a][b] = 0;
		for (a = 0; a <= n; a++)
			for (b = 0; b <= a; b++) {
				int x = dq[a][b];

				if (x == 0)
					continue;
				if (cc[i] == '(' || cc[i] == 'x') {
					if (b > 0)
						dq_[a][b - 1] = (dq_[a][b - 1] + x) % MD;
					else {
						for (d = 2; d <= n; d += 2)
							if (a + 1 >= d / 2)
								ans = (ans + (long long) dp[i][d - 1] * x) % MD;
							else {
								a_ = a + d / 2, b_ = d / 2 - (a + 1);
								dr_[a_][b_] = (dr_[a_][b_] + x) % MD;
							}
					}
				}
				if (cc[i] == ')' || cc[i] == 'x') {
					if (b < a)
						dq_[a][b + 1] = (dq_[a][b + 1] + x) % MD;
					else
						dq_[a + 1][b + 1] = (dq_[a + 1][b + 1] + x) % MD;
				}
			}
		for (a = 0; a <= n; a++)
			for (b = 0; b <= a; b++) {
				int x = dr[a][b];

				if (x == 0)
					continue;
				if (cc[i] == '(' || cc[i] == 'x') {
					if (b > 1)
						dr_[a][b - 1] = (dr_[a][b - 1] + x) % MD;
					else
						ans = (ans + (long long) dp[i][a] * x) % MD;
				}
				if (cc[i] == ')' || cc[i] == 'x') {
					if (b < a)
						dr_[a][b + 1] = (dr_[a][b + 1] + x) % MD;
				}
			}
		for (a = 0; a <= n; a++)
			for (b = 0; b <= a; b++)
				dq[a][b] = dq_[a][b], dr[a][b] = dr_[a][b];
	}
	return ans;
}

int solve3(char *cc, int n) {
	static int dp[N + 1][N + 1], dp_[N + 1][N + 1], dq[N + 1][N + 1], dr[N + 1], dr_[N + 1], xx[2][N + 1];
	int r, i, j, a, b, d, ans;

	for (r = 0; r < 2; r++) {
		for (a = 0; a <= n; a++)
			for (b = 0; b <= a; b++)
				dp[a][b] = 0;
		dp[0][0] = 1;
		for (i = 0; i < n; i++) {
			for (a = n; a >= 0; a--)
				dq[i][a] = ((a == n ? 0 : dq[i][a + 1]) + dp[a][0]) % MD;
			for (a = 0; a <= n; a++)
				for (b = 0; b <= a; b++)
					dp_[a][b] = 0;
			for (a = 0; a <= n; a++)
				for (b = 0; b <= a; b++) {
					int x = dp[a][b];

					if (x == 0)
						continue;
					if (cc[i] == '(' || cc[i] == 'x') {
						if (b < a)
							dp_[a][b + 1] = (dp_[a][b + 1] + x) % MD;
						else
							dp_[a + 1][b + 1] = (dp_[a + 1][b + 1] + x) % MD;
					}
					if ((cc[i] == ')' || cc[i] == 'x') && b > 0)
						dp_[a][b - 1] = (dp_[a][b - 1] + x) % MD;
				}
			for (a = 0; a <= n; a++)
				for (b = 0; b <= a; b++)
					dp[a][b] = dp_[a][b];
		}
		for (j = 0; j < n; j++) {
			memset(dr, 0, (n + 1) * sizeof *dr), dr[0] = 1;
			for (i = j; i >= 0; i--) {
				if (cc[i] == ')' || cc[i] == 'x') {
					for (d = 0; d <= n; d++)
						xx[r][j + 1] = (xx[r][j + 1] + (long long) dq[i][d / 2] * dr[d]) % MD;
				}
				memset(dr_, 0, (n + 1) * sizeof *dr_);
				for (d = 0; d <= n; d++) {
					int x = dr[d];

					if (x == 0)
						continue;
					if (cc[i] == '(' || cc[i] == 'x')
						dr_[d + 1] = (dr_[d + 1] + x) % MD;
					if ((cc[i] == ')' || cc[i] == 'x') && d > r)
						dr_[d - 1] = (dr_[d - 1] + x) % MD;
				}
				memcpy(dr, dr_, (n + 1) * sizeof *dr_);
			}
		}
		flip(cc, n);
	}
	ans = 0;
	for (i = 1; i < n; i++)
		ans = (ans + (long long) xx[0][i] * xx[1][n - i]) % MD;
	return ans;
}

int main() {
	static char cc[N + 1];
	int n, r, ans;

	scanf("%d%s", &n, cc);
	if (n % 2 != 0) {
		printf("0\n");
		return 0;
	}
	ans = solve1(cc, n);
	for (r = 0; r < 2; r++) {
		ans = (ans + solve2(cc, n)) % MD;
		flip(cc, n);
	}
	ans = (ans + solve3(cc, n)) % MD;
	printf("%d\n", ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

securitygate.c: In function 'main':
securitygate.c:183:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 43 / 43
• Subtask 5: 27 / 27