Submission #96964

#	Time	Username	Problem	Language	Result	Execution time	Memory
96964		diamond_duke	Security Gate (JOI18_security_gate)	C++11	100 / 100	1407 ms	671772 KiB

securitygate

#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
constexpr int MOD = 1e9 + 7;
inline void add(int &x, const int &y) { (x += y) >= MOD ? (x -= MOD) : 0; }
int n, arr[305], any[305][305], dp_l[155][305][305][2];
namespace solver_1 { int dp_r[305][305][305][2]; }
namespace solver_2 { int dp_r[155][305][605][3]; }
inline void init_any()
{
	memset(any, 0, sizeof(any));
	any[n][0] = 1;
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j <= n; j++)
		{
			if (!any[i + 1][j])
				continue;
			if (arr[i] != +1 && j < n)
				add(any[i][j + 1], any[i + 1][j]);
			if (arr[i] != -1 && j > 0)
				add(any[i][j - 1], any[i + 1][j]);
		}
	}
}
inline void init_dp_l()
{
	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 (arr[i] != -1 && j < a)
						add(dp[i + 1][j + 1][x || j + 1 == a], dp[i][j][x]);
					if (arr[i] != +1 && j > 0)
						add(dp[i + 1][j - 1][x], dp[i][j][x]);
				}
			}
		}
	}
}
inline int solve_1()
{
	using namespace solver_1;
	memset(dp_r, 0, sizeof(dp_r));
	for (int a = 0; a < n; a++)
	{
		auto dp = dp_r[a];
		dp[n][0][!a] = 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)
					add(dp[i][j + 1][0], dp[i + 1][j][0]);
				if (arr[i] != -1 && j > 0)
					add(dp[i][j - 1][0], dp[i + 1][j][0]);
			}
			if (arr[i] != -1 && a < n)
				add(dp[i][a][1], dp[i + 1][a + 1][0]);
			if (arr[i] != +1 && a > 0)
				add(dp[i][a][1], dp[i + 1][a - 1][0]);
			for (int j = 0; j <= std::min(a * 2, n - 1); j++)
			{
				if (!dp[i + 1][j][1])
					continue;
				if (arr[i] != +1 && j >= a)
					add(dp[i][j + 1][1], dp[i + 1][j][1]);
				if (arr[i] != -1 && j >= a + 2)
					add(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 ? any[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;
			}
		}
	}
	return res;
}
inline int solve_2(int t)
{
	using namespace solver_2;
	memset(dp_r, 0, sizeof(dp_r));
	for (int a = 0; a < n / 2; a++)
	{
		auto dp = dp_r[a];
		dp[n][n][!(a + t)] = 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)
					add(dp[i][j + 1 + n][j + 1 == a + t], dp[i + 1][j + n][0]);
				if (arr[i] != -1 && j > 0)
					add(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)
					add(dp[i][j + 1 + n][1], dp[i + 1][j + n][1]);
				if (arr[i] != -1)
					add(dp[i][j - 1 + n][1 + !j], dp[i + 1][j + n][1]);
			}
			for (int j = -n; j <= std::min(a * 2, n - 1); j++)
			{
				if (!dp[i + 1][j + n][2])
					continue;
				if (arr[i] != +1 && j < a * 2)
					add(dp[i][j + 1 + n][2], dp[i + 1][j + n][2]);
				if (arr[i] != -1 && j > -n)
					add(dp[i][j - 1 + n][2], dp[i + 1][j + n][2]);
			}
		}
	}
	int res = 0;
	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()
{
	// freopen("JOISC2018-D3T3.in", "r", stdin);
	scanf("%d%s", &n, str);
	for (int i = 0; i < n; i++)
		arr[i] = str[i] == '(' ? 1 : str[i] == ')' ? -1 : 0;
	init_any();
	int ans = any[0][0];
	init_dp_l();
	add(ans, solve_1());
	add(ans, solve_2(0));
	std::reverse(arr, arr + n);
	for (int i = 0; i < n; i++)
		arr[i] = -arr[i];
	init_any();
	init_dp_l();
	add(ans, solve_1());
	add(ans, solve_2(1));
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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