Submission #99162

#	Time	Username	Problem	Language	Result	Execution time	Memory
99162		diamond_duke	Security Gate (JOI18_security_gate)	C++11	100 / 100	2049 ms	774684 KiB

securitygate

#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
constexpr int MOD = 1e9 + 7;
inline void upd(int &x, int y) { (x += y) >= MOD ? (x -= MOD) : 0; }
int arr[305], all[305][305], dp_l[155][305][305][2], dp_r[305][305][605][3];
inline int solve(int n, int off)
{
	memset(all, 0, sizeof(all));
	all[n][0] = 1;
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j <= n; j++)
		{
			if (!all[i + 1][j])
				continue;
			if (arr[i] != 1 && j != n)
				upd(all[i][j + 1], all[i + 1][j]);
			if (arr[i] != -1 && j)
				upd(all[i][j - 1], all[i + 1][j]);
		}
	}
	memset(dp_l, 0, sizeof(dp_l));
	for (int x = 0; x < n / 2; x++)
	{
		auto dp = dp_l[x];
		dp[0][0][!x] = 1;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j <= x; j++)
			{
				for (int flg = 0; flg < 2; flg++)
				{
					if (!dp[i][j][flg])
						continue;
					if (arr[i] != 1 && j)
						upd(dp[i + 1][j - 1][flg], dp[i][j][flg]);
					if (arr[i] != -1 && j != x)
						upd(dp[i + 1][j + 1][flg || j + 1 == x], dp[i][j][flg]);
				}
			}
		}
	}
	memset(dp_r, 0, sizeof(dp_r));
	for (int x = 0; x < n; x++)
	{
		auto dp = dp_r[x];
		dp[n][0][!x] = 1;
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = 0; j <= n; j++)
			{
				if (!dp[i + 1][j][0])
					continue;
				if (arr[i] != 1 && j < n)
					upd(dp[i][j + 1][0], dp[i + 1][j][0]);
				if (arr[i] != -1 && j)
					upd(dp[i][j - 1][0], dp[i + 1][j][0]);
			}
			if (arr[i] != 1 && x)
				upd(dp[i][x][1], dp[i + 1][x - 1][0]);
			if (arr[i] != -1 && x < n)
				upd(dp[i][x][1], dp[i + 1][x + 1][0]);
			for (int j = x; j <= std::min(x * 2, n - 1); j++)
			{
				if (!dp[i + 1][j][1])
					continue;
				if (arr[i] != 1)
					upd(dp[i][j + 1][1], dp[i + 1][j][1]);
				if (arr[i] != -1 && j >= x + 2)
					upd(dp[i][j - 1][1], dp[i + 1][j][1]);
			}
		}
	}
	int res = 0;
	for (int a = 0; a <= n / 2; a++)
	{
		for (int b = 1; a + b <= n / 2; b++)
		{
			for (int pos = 0; pos < n; pos += 2)
			{
				if (arr[pos] == 1)
					continue;
				int val = a >= b ? all[pos + 1][2 * b - 1] : dp_r[a + b][pos + 1][2 * b - 1][1];
				res = (res + (ll)dp_l[a][pos][0][1] * val) % MOD;
			}
		}
	}
	memset(dp_r, 0, sizeof(dp_r));
	for (int x = 0; x < n / 2; x++)
	{
		auto dp = dp_r[x];
		dp[n][n][!(x + off)] = 1;
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = 0; j <= n; j++)
			{
				if (!dp[i + 1][j + n][0])
					continue;
				if (arr[i] != 1 && j < n)
					upd(dp[i][j + 1 + n][j + 1 == x + off], dp[i + 1][j + n][0]);
				if (arr[i] != -1)
					upd(dp[i][j - 1 + n][0], dp[i + 1][j + n][0]);
			}
			for (int j = 0; j <= n; j++)
			{
				if (!dp[i + 1][j + n][1])
					continue;
				if (arr[i] != 1)
					upd(dp[i][j + 1 + n][1], dp[i + 1][j + n][1]);
				if (arr[i] != -1)
					upd(dp[i][j - 1 + n][1 + !j], dp[i + 1][j + n][1]);
			}
			for (int j = -n; j <= std::min(x * 2, n - 1); j++)
			{
				if (!dp[i + 1][j + n][2])
					continue;
				if (arr[i] != 1 && j != x * 2)
					upd(dp[i][j + 1 + n][2], dp[i + 1][j + n][2]);
				if (arr[i] != -1 && j != -n)
					upd(dp[i][j - 1 + n][2], dp[i + 1][j + n][2]);
			}
		}
	}
	for (int a = 0; a <= n / 2; a++)
	{
		for (int b = -n / 2 + 1; b < n / 2; b++)
		{
			if (a + b < 0 || a + (b < 0 ? -b : b) >= n / 2)
				continue;
			for (int pos = 0; pos < n; pos += 2)
			{
				if (arr[pos] == 1)
					continue;
				res = (res + (ll)dp_l[a][pos][0][1] * dp_r[a + b][pos + 1][b * 2 - 1 + n][2]) % MOD;
			}
		}
	}
	return res;
}
char str[305];
int main()
{
	int n;
	scanf("%d%s", &n, str);
	for (int i = 0; i < n; i++)
		arr[i] = str[i] == '(' ? 1 : str[i] == ')' ? -1 : 0;
	int ans = solve(n, 0);
	upd(ans, all[0][0]);
	for (int i = 0; i < n; i++)
		arr[i] *= -1;
	std::reverse(arr, arr + n);
	upd(ans, solve(n, 1));
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

securitygate.cpp: In function 'int main()':
securitygate.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%s", &n, str);
  ~~~~~^~~~~~~~~~~~~~~~~

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