Submission #1222578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222578		PenguinsAreCute	Security Gate (JOI18_security_gate)	C++17	73 / 100	1534 ms	1114112 KiB

securitygate

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int pre1[n+1][n+1][n+1];
	int suff1[n+1][n+1][n+1];
	int pre2[n+1][n+1][n+1][2];
	int suff2[n+1][n+1][n+1][2];
	int mid[n+1][n+1][2*n+1][n+1];
	memset(pre1,0,sizeof(pre1));
	memset(suff1,0,sizeof(suff1));
	memset(pre2,0,sizeof(pre2));
	memset(suff2,0,sizeof(suff2));
	memset(mid,0,sizeof(mid));
	pre1[0][0][0] = suff1[n][0][0] = 1;
	for(int x=0;x<=n;x++)
		pre2[0][0][x][0] = suff2[n][0][x][0] = 1;
	for(int i=0;i<n;i++) {
		if(s[i] != ')')
			for(int j=0;j<n;j++)
				for(int k=0;k<=n;k++)
					(pre1[i+1][j+1][max(k,j+1)] += pre1[i][j][k]) %= MOD;
		if(s[i] != '(')
			for(int j=1;j<n;j++)
				for(int k=0;k<=n;k++)
					(pre1[i+1][j-1][max(k,j-1)] += pre1[i][j][k]) %= MOD;
	}
	for(int i=0;i<n;i++) {
		if(s[i] != ')')
			for(int j=0;j<n;j++)
				for(int x=0;x<=n;x++)
					for(int z=0;z<2;z++)
						(pre2[i+1][j+1][x][(j+1==2*x+1?1:(j+1==x?0:z))] += pre2[i][j][x][z]) %= MOD;
		if(s[i] != '(')
			for(int j=1;j<=n;j++)
				for(int x=0;x<=n;x++)
					for(int z=0;z<2;z++)
						(pre2[i+1][j-1][x][(j-1==2*x+1?1:(j-1==x?0:z))] += pre2[i][j][x][z]) %= MOD;
	}
	for(int i=n;i--;) {
		if(s[i] != ')')
			for(int j=0;j<n;j++)
				for(int k=0;k<=n;k++)
					(suff1[i][j][max(j,k)] += suff1[i+1][j+1][k]) %= MOD;
		if(s[i] != '(')
			for(int j=1;j<=n;j++)
				for(int k=0;k<=n;k++)
					(suff1[i][j][max(j,k)] += suff1[i+1][j-1][k]) %= MOD;
	}
	for(int i=n;i--;) {
		if(s[i] != ')')
			for(int j=0;j<n;j++)
				for(int x=0;x<=n;x++)
					for(int z=0;z<2;z++)
						(suff2[i][j][x][(j==2*x+1?1:(j==x?0:z))] += suff2[i+1][j+1][x][z]) %= MOD;
		if(s[i] != '(')
			for(int j=1;j<=n;j++)
				for(int x=0;x<=n;x++)
					for(int z=0;z<2;z++)
						(suff2[i][j][x][(j==2*x+1?1:(j==x?0:z))] += suff2[i+1][j-1][x][z]) %= MOD;
	}
	for(int l=0;l<=n;l++) {
		mid[l][l][n][0] = 1;
		for(int r=l;r<n;r++) {
			if(s[r] != ')')
				for(int j=0;j<2*n;j++)
					for(int k=n;k<=2*n;k++)
						(mid[l][r+1][j+1][max(j+1,k)-n] += mid[l][r][j][k-n]) %= MOD;
			if(s[r] != '(')
				for(int j=1;j<=2*n;j++)
					for(int k=n;k<=2*n;k++)
						(mid[l][r+1][j-1][max(j-1,k)-n] += mid[l][r][j][k-n]) %= MOD;
		}
	}
	for(int l=0;l<=n;l++)
		for(int r=l;r<=n;r++)
			for(int j=0;j<=2*n;j++)
				for(int k=n+1;k<=2*n;k++)
					(mid[l][r][j][k-n] += mid[l][r][j][k-n-1]) %= MOD;
	int ans = 0;
	for(int i=0;i<=n;i++)
		(ans += pre1[n][0][i]) %= MOD;
	for(int l=1;l<=n;l++)
		for(int r=l;r<n;r++) if(s[l-1] != '(' && s[r] != ')') {
			int pre1suff[n+1], suff1suff[n+1];
			pre1suff[n] = pre1[l-1][0][n];
			for(int i=n;i--;)
				pre1suff[i] = (pre1suff[i+1] + pre1[l-1][0][i]) % MOD;
			suff1suff[n] = suff1[r+1][0][n];
			for(int i=n;i--;)
				suff1suff[i] = (suff1suff[i+1] + suff1[r+1][0][i]) % MOD;
			for(int tot=-n+(n&1);tot<=n;tot+=2)
				for(int midheight=n-(n&1),prev=0;midheight>=max(0,tot);midheight-=2) {
					int ways = 1LL * pre1suff[midheight / 2] * suff1suff[midheight / 2 - tot / 2] % MOD;
					ways = (ways - exchange(prev, ways) + MOD) % MOD;
					ways = 1LL * ways * mid[l][r][tot+n][min(n,midheight+1)] % MOD;
					(ans += ways) %= MOD;
				}
		}
	for(int i=1;i<=n;i++) if(s[i-1] != ')')
		for(int j=0;j<=n;j++)
			for(int k=2;k<=n;k+=2) {
				int ways = suff1[i][0][j];
				int tar = (k / 2) + j;
				if(tar >= k || 2 * tar + 1 > n)
					ways = 1LL * ways * (pre2[i-1][k-1][0][0] + pre2[i-1][k-1][0][1]) % MOD;
				else
					ways = 1LL * ways * pre2[i-1][k-1][tar][0] % MOD;
				(ans += ways) %= MOD;
			}
	for(int i=0;i<n;i++) if(s[i] != '(')
		for(int j=0;j<=n;j++)
			for(int k=2;k<=n;k+=2) {
				int ways = pre1[i][0][j];
				int tar = (k / 2) + j;
				if(tar >= k || 2 * tar + 1 > n)
					ways = 1LL * ways * (suff2[i+1][k-1][0][0] + suff2[i+1][k-1][0][1]) % MOD;
				else
					ways = 1LL * ways * suff2[i+1][k-1][tar][0] % MOD;
				(ans += ways) %= MOD;
			}
	cout << ans;
}

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