Submission #95843

#	Time	Username	Problem	Language	Result	Execution time	Memory
95843		diamond_duke	Security Gate (JOI18_security_gate)	C++11	100 / 100	1488 ms	784988 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], n;
namespace solver_0
{
	int dp[305][305];
	int solve()
	{
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j <= n; j++)
			{
				if (!dp[i][j])
					continue;
				if (arr[i] != -1 && j != n)
					upd(dp[i + 1][j + 1], dp[i][j]);
				if (arr[i] != 1 && j)
					upd(dp[i + 1][j - 1], dp[i][j]);
			}
		}
		return dp[n][0];
	}
}
namespace solver_1
{
	int dp_l[155][305][305][2], dp_r[305][305][305][2], suf[305][305];
	int solve()
	{
		memset(dp_l, 0, sizeof(dp_l));
		for (int a = 0; a < n / 2; a++)
		{
			auto dp = dp_l[a];
			dp[0][0][!a] = 1;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j <= a; j++)
				{
					for (int x = 0; x < 2; x++)
					{
						if (!dp[i][j][x])
							continue;
						if (j != a && arr[i] != -1)
							upd(dp[i + 1][j + 1][x || j + 1 == a], dp[i][j][x]);
						if (j && arr[i] != 1)
							upd(dp[i + 1][j - 1][x], dp[i][j][x]);
					}
				}
			}
		}
		memset(dp_r, 0, sizeof(dp_r));
		for (int c = 0; c < n; c++)
		{
			auto dp = dp_r[c];
			dp[n][0][!c] = 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)
						upd(dp[i][j + 1][0], dp[i + 1][j][0]);
					if (j && arr[i] != -1)
						upd(dp[i][j - 1][0], dp[i + 1][j][0]);
				}
				if (c && arr[i] != 1)
					upd(dp[i][c][1], dp[i + 1][c - 1][0]);
				if (arr[i] != -1)
					upd(dp[i][c][1], dp[i + 1][c + 1][0]);
				for (int j = 0; j <= std::min(c * 2, n - 1); j++)
				{
					if (!dp[i + 1][j][1])
						continue;
					if (j >= c && arr[i] != 1)
						upd(dp[i][j + 1][1], dp[i + 1][j][1]);
					if (j >= c + 2 && arr[i] != -1)
						upd(dp[i][j - 1][1], dp[i + 1][j][1]);
				}
			}
		}
		memset(suf, 0, sizeof(suf));
		suf[n][0] = 1;
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = 0; j <= n; j++)
			{
				if (j != n && arr[i] != 1)
					upd(suf[i][j + 1], suf[i + 1][j]);
				if (j && arr[i] != -1)
					upd(suf[i][j - 1], suf[i + 1][j]);
			}
		}
		int res = 0;
		for (int a = 0; a <= n / 2; a++)
		{
			for (int c = 1; a + c <= n / 2; c++)
			{
				for (int len = 0; len < n; len += 2)
				{
					if (arr[len] == 1)
						continue;
					int coef = a >= c ? suf[len + 1][2 * c - 1] :
							   dp_r[a + c][len + 1][2 * c - 1][1];
					res = (res + (ll)dp_l[a][len][0][1] * coef) % MOD;
				}
			}
		}
		return res;
	}
}
namespace solver_2
{
	int dp_l[155][305][305][2], dp_r[155][305][605][3];
	void init(int add)
	{
		memset(dp_l, 0, sizeof(dp_l));
		for (int a = 0; a < n / 2; a++)
		{
			auto dp = dp_l[a];
			dp[0][0][!a] = 1;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j <= a; j++)
				{
					for (int x = 0; x < 2; x++)
					{
						if (!dp[i][j][x])
							continue;
						if (j != a && arr[i] != -1)
							upd(dp[i + 1][j + 1][x || j + 1 == a], dp[i][j][x]);
						if (j && arr[i] != 1)
							upd(dp[i + 1][j - 1][x], dp[i][j][x]);
					}
				}
			}
		}
		memset(dp_r, 0, sizeof(dp_r));
		for (int c = 0; c < n / 2; c++)
		{
			auto dp = dp_r[c];
			dp[n][n][!(c + add)] = 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)
						upd(dp[i][j + 1 + n][j + 1 == c + add], dp[i + 1][j + n][0]);
					if (j && 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(c * 2, n - 1); j++)
				{
					if (!dp[i + 1][j + n][2])
						continue;
					if (j != c * 2 && arr[i] != 1)
						upd(dp[i][j + 1 + n][2], dp[i + 1][j + n][2]);
					if (j != -n && arr[i] != -1)
						upd(dp[i][j - 1 + n][2], dp[i + 1][j + n][2]);
				}
			}
		}
	}
	int solve()
	{
		int res = 0;
		for (int t = 0; t < 2; t++)
		{
			init(t);
			for (int a = 0; a <= n / 2; a++)
			{
				for (int c = -n / 2 + 1; c < n / 2; c++)
				{
					if (a + c < 0 || a + (c < 0 ? -c : c) >= n / 2)
						continue;
					for (int len = 0; len < n; len += 2)
					{
						if (arr[len] == 1)
							continue;
						res = (res + (ll)dp_l[a][len][0][1] *
							   dp_r[a + c][len + 1][c * 2 - 1 + n][2]) % MOD;
					}
				}
			}
			std::reverse(arr, arr + n);
			for (int i = 0; i < n; i++)
				arr[i] *= -1;
		}
		return res;
	}
}
char str[305];
int main()
{
	// freopen("loj-2839.in", "r", stdin);
	scanf("%d%s", &n, str);
	if (n & 1)
	{
		puts("0");
		return 0;
	}
	for (int i = 0; i < n; i++)
		arr[i] = str[i] == '(' ? 1 : str[i] == ')' ? -1 : 0;
	int ans = solver_0::solve();
	for (int t = 0; t < 2; t++)
	{
		upd(ans, solver_1::solve());
		std::reverse(arr, arr + n);
		for (int i = 0; i < n; i++)
			arr[i] *= -1;
	}
	upd(ans, solver_2::solve());
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

securitygate.cpp: In function 'int main()':
securitygate.cpp:212: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