Submission #1222565

#TimeUsernameProblemLanguageResultExecution timeMemory
1222565PenguinsAreCuteSecurity Gate (JOI18_security_gate)C++17
0 / 100
5079 ms834932 KiB
#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]; 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++) for(int tot=-n+(n&1);tot<=n;tot+=2) for(int maxl=0;maxl<=n;maxl++) for(int maxr=0;maxr<=n;maxr++) { if(s[l-1] == '(' || s[r] == ')') continue; int ways = 1LL * pre1[l-1][0][maxl] * suff1[r+1][0][maxr] % MOD; int psum = tot / 2; int midheight = 2 * min(maxl, maxr + psum); if(midheight < max(0, tot)) continue; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...