Submission #1030181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030181		MilosMilutinovic	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++14	51 / 100	1657 ms	12860 KiB

festival2

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int md;
int dp[N][N][4][3];
int new_dp[N][N][4][3];

int add(int x, int y) {
  return x + y < md ? x + y : x + y - md;
}

void ckadd(int& x, int y) {
  x = add(x, y);
}

int mul(int x, int y) {
  return x * 1LL * y % md;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> md;
  dp[0][0][1][0] = 1;
  for (int pos = 1; pos <= 2 * n; pos++) {
    for (int bal = 0; bal <= n; bal++) {
      for (int bef = 0; bef <= n; bef++) {
        for (int rd = 0; rd < 4; rd++) {
          for (int b = 0; b < 3; b++) {
            if (dp[bal][bef][rd][b] == 0) {
              continue;
            }
            int open = bal;
            int close = open - bal;
            {
              // take open bracket
              int new_bal = bal + 1;
              int new_bef = bef;
              int new_rd = rd;
              int new_b = (b == 0 ? 2 : b);
              if (b == 0) {
                new_rd--;
              }
              ckadd(new_dp[new_bal][new_bef][new_rd][new_b], dp[bal][bef][rd][b]);
            }
            if (bal > 0) {
              // take close bracket
              if (b != 0) {
                // match last bad greedy bracket
                if (b == 1) {
                  int new_bal = bal - 1;
                  int new_bef = bef - 1;
                  int new_rd = rd;
                  int new_b = 0;
                  ckadd(new_dp[new_bal][new_bef][new_rd][new_b], dp[bal][bef][rd][b]);
                } else {
                  int new_bal = bal - 1;
                  int new_bef = open - 1;
                  int new_rd = min(3, rd + 1);
                  int new_b = 0;
                  ckadd(new_dp[new_bal][new_bef][new_rd][new_b], dp[bal][bef][rd][b]);
                }
              }
              // match with bracket that is not last bad greedy bracket
              {
                // match with bracket before last opt greedy
                int new_bal = bal - 1;
                int new_bef = bef - 1;
                int new_rd = rd;
                int new_b = b;
                int ft = bef - (b == 1);
                ckadd(new_dp[new_bal][new_bef][new_rd][new_b], mul(dp[bal][bef][rd][b], ft));
              }
              {
                // match with bracket after last opt greedy
                int new_bal = bal - 1;
                int new_bef = open - 1;
                int new_rd = min(3, rd + 1);
                int new_b = (b != 0 ? 1 : 0);
                int ft = (open - bef) - (b == 2);
                ckadd(new_dp[new_bal][new_bef][new_rd][new_b], mul(dp[bal][bef][rd][b], ft));
              }
            }
          }
        }
      }
    }
    for (int bal = 0; bal <= n; bal++) {
      for (int bef = 0; bef <= n; bef++) {
        for (int rd = 0; rd < 4; rd++) {
          for (int b = 0; b < 3; b++) {
            dp[bal][bef][rd][b] = new_dp[bal][bef][rd][b];
            new_dp[bal][bef][rd][b] = 0;
          }
        }
      }
    }
  }
  int res = 0;
  for (int bef = 0; bef <= n; bef++) {
    for (int rd = 2; rd < 4; rd++) {
      ckadd(res, dp[0][bef][rd][0]);
    }
  }
  cout << res << '\n';
  return 0;
}

Compilation message (stderr)

festival2.cpp: In function 'int main()':
festival2.cpp:38:17: warning: unused variable 'close' [-Wunused-variable]
   38 |             int close = open - bal;
      |                 ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 27 / 27
• Subtask 4: 14 / 14
• Subtask 5: 0 / 36
• Subtask 6: 0 / 13