Submission #224524

#	Time	Username	Problem	Language	Result	Execution time	Memory
224524		rama_pang	Security Gate (JOI18_security_gate)	C++14	100 / 100	1523 ms	665724 KiB

securitygate

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 305;

void RADD(int &a, int b) { if ((a += b) >= MOD) a -= MOD; }
int MUL(int a, int b) { return 1ll * a * b % MOD; }

int n;
string a;

int dp_valid[MAXN][MAXN];
int dp_l[MAXN / 2][MAXN][MAXN][2]; // dp[A][pos][bal][done?], A: max height from left without going negitive

int dp_r_one[MAXN][MAXN][MAXN][2]; // dp[A + B/2][pos][bal][fixed?], B: final height
int dp_r_both[MAXN / 2][MAXN][2 * MAXN][3]; // dp[A][pos][bal + n][init/foundA/neg], A: max height from right without going negative

void calc_dp_valid() {
  memset(dp_valid, 0, sizeof(dp_valid));

  auto dp = dp_valid;
  dp[n][0] = 1;

  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j <= n; j++) {
      if (a[i] != ')' && j < n) {
        RADD(dp[i][j], dp[i + 1][j + 1]);
      }
      if (a[i] != '(' && j > 0) {
        RADD(dp[i][j], dp[i + 1][j - 1]);
      }
    }
  }
}

void calc_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++) { // pos
      for (int j = 0; j <= A; j++) { // bal
        for (int k = 0; k < 2; k++) { // done?
          if (a[i] != ')' && j < A) {
            RADD(dp[i + 1][j + 1][k || j + 1 == A], dp[i][j][k]);
          }
          if (a[i] != '(' && j > 0) {
            RADD(dp[i + 1][j - 1][k], dp[i][j][k]);
          }
        }
      }
    }
  }
}

void calc_dp_r_one() {
  memset(dp_r_one, 0, sizeof(dp_r_one));
  
  for (int M = 0; M <= n; M++) { // M = A + B/2
    auto dp = dp_r_one[M];
    dp[n][0][!M] = 1;

    for (int i = n - 1; i >= 0; i--) { // pos
      // not yet fixed M transition
      for (int j = 0; j <= n; j++) { // bal
        if (a[i] != ')' && j < n) {
          RADD(dp[i][j][0], dp[i + 1][j + 1][0]);
        }
        if (a[i] != '(' && j > 0) {
          RADD(dp[i][j][0], dp[i + 1][j - 1][0]);
        }
      }

      // unfixed -> fixed M transition
      if (a[i] != ')' && M < n) {
        RADD(dp[i][M][1], dp[i + 1][M + 1][0]);
      }
      if (a[i] != '(' && M > 0) {
        RADD(dp[i][M][1], dp[i + 1][M - 1][0]);
      }

      // fixed M transition, balance mus stay strictly above M
      for (int j = M + 1; j <= min(2 * M, n - 1); j++) { // X <= 2A + B = 2M, so X <= 2M
        if (a[i] != ')' && j < 2 * M) {
          RADD(dp[i][j][1], dp[i + 1][j + 1][1]);
        } 
        if (a[i] != '(' && j > 0){
          RADD(dp[i][j][1], dp[i + 1][j - 1][1]);
        }
      }
    }
  }
}

void calc_dp_r_both(int not_include_zero) {
  memset(dp_r_both, 0, sizeof(dp_r_both));
  
  for (int A = 0; A <= n / 2; A++) { // maximum height viewed from the right
    auto dp = dp_r_both[A];
    dp[n][n][!(A + not_include_zero)] = 1;

    for (int i = n - 1; i >= 0; i--) { // pos
      // haven't seen A
      for (int j = 0; j <= n; j++) { // bal
        if (a[i] != '(' && j < n) {
          RADD(dp[i][j + 1 + n][j + 1 == A + not_include_zero], dp[i + 1][j + n][0]);
        }
        if (a[i] != ')' && j > 0) {
          RADD(dp[i][j - 1 + n][0], dp[i + 1][j + n][0]);
        }
      }

      // seen A
      for (int j = 0; j <= n; j++) {
        if (a[i] != '(') {
          RADD(dp[i][j + 1 + n][1], dp[i + 1][j + n][1]);
        }
        if (a[i] != ')') {
          RADD(dp[i][j - 1 + n][1 + !j], dp[i + 1][j + n][1]);
        }
      }

      // gone negative
      for (int j = - n; j <= min(2 * A, n - 1); j++) {
        if (a[i] != '(' && j < 2 * A) {
          RADD(dp[i][j + 1 + n][2], dp[i + 1][j + n][2]);
        }
        if (a[i] != ')' && j > - n) {
          RADD(dp[i][j - 1 + n][2], dp[i + 1][j + n][2]);
        }
      }
    }
  }
}

int invalid_one() {
  int res = 0;
  for (int A = 0; A <= n / 2; A++) { // maximum before going negative from the left
    for (int B = 2; B <= n; B += 2) { // B = final height on the right
      for (int pos = 0; pos < n; pos += 2) {
        if (a[pos] == '(') continue;
        int val = A >= B / 2 ? dp_valid[pos + 1][B - 1] : dp_r_one[A + B / 2][pos + 1][B - 1][1];
        RADD(res, MUL(dp_l[A][pos][0][1], val));
      }
    }
  }
  return res;
}

int invalid_both() {
  int res = 0;
  for (int A = 0; A <= n / 2; A++) {
    for (int B = - n + 2; B < n; B += 2) {
      if (A + B / 2 < 0 || A + abs(B / 2) >= n / 2) continue;
      for (int pos = 0; pos < n; pos += 2) {
        if (a[pos] == '(') continue;
        RADD(res, MUL(dp_l[A][pos][0][1], dp_r_both[A + B / 2][pos + 1][B - 1 + n][2]));
      }
    }
  }
  return res;
}

int Solve() {
  if (n & 1) return 0;
  
  calc_dp_valid();
  calc_dp_l();
  calc_dp_r_one();
  calc_dp_r_both(0);

  int res = dp_valid[0][0];

  RADD(res, invalid_one());
  RADD(res, invalid_both());

  reverse(begin(a), end(a));
  for (int i = 0; i < n; i++) {
    if (a[i] == '(') {
      a[i] = ')';
    } else if (a[i] == ')') {
      a[i] = '(';
    }
  }

  calc_dp_valid();
  calc_dp_l();
  calc_dp_r_one();
  calc_dp_r_both(1);

  RADD(res, invalid_one());
  RADD(res, invalid_both());

  return res;
}

int main() {
  cin >> n >> a;
  cout << Solve() << "\n";
  return 0;
}

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