oj.uz

Submission #1030174

# Submission time Handle Problem Language Result Execution time Memory
1030174 2024-07-21T22:16:56 Z MilosMilutinovic Festivals in JOI Kingdom 2 (JOI23_festival2) C++14
37 / 100
 299 ms 9304 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 33;

int md;
int dp[2 * N][N][N][4][2][2];

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][0][1][0][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 o = 0; o < 2; o++) {
            for (int b = 0; b < 2; b++) {
              if (dp[pos - 1][bal][bef][rd][o][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_o = 1;
                int new_b = (o == 1 ? b : 0);
                if (o == 0) {
                  new_rd--;
                }
                ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], dp[pos - 1][bal][bef][rd][o][b]);
              }
              if (bal > 0) {
                // take close bracket
                if (o == 1) {
                  // match last bad greedy bracket
                  if (b == 1) {
                    int new_bal = bal - 1;
                    int new_bef = bef - 1;
                    int new_rd = rd;
                    int new_o = 0;
                    int new_b = 0;
                    ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], dp[pos - 1][bal][bef][rd][o][b]);
                  } else {
                    int new_bal = bal - 1;
                    int new_bef = open - 1;
                    int new_rd = min(3, rd + 1);
                    int new_o = 0;
                    int new_b = 0;
                    ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], dp[pos - 1][bal][bef][rd][o][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_o = o;
                  int new_b = b;
                  int ft = bef - (o == 1 && b == 1);
                  ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], mul(dp[pos - 1][bal][bef][rd][o][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_o = o;
                  int new_b = (o == 1 ? 1 : 0);
                  int ft = (open - bef) - (o == 1 && b == 0);
                  ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], mul(dp[pos - 1][bal][bef][rd][o][b], ft));
                }
              }
            }
          }
        }
      }
    }
  }
  int res = 0;
  for (int bef = 0; bef <= n; bef++) {
    for (int rd = 2; rd < 4; rd++) {
      ckadd(res, dp[2 * n][0][bef][rd][0][0]);
    }
  }
  cout << res << '\n';
  return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 3 ms 3420 KB Output is correct
16 Correct 3 ms 3164 KB Output is correct
17 Correct 1 ms 1624 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 3 ms 3420 KB Output is correct
16 Correct 3 ms 3164 KB Output is correct
17 Correct 1 ms 1624 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Runtime error 299 ms 9304 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 3 ms 3420 KB Output is correct
16 Correct 3 ms 3164 KB Output is correct
17 Correct 1 ms 1624 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Runtime error 299 ms 9304 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 3 ms 3420 KB Output is correct
16 Correct 3 ms 3164 KB Output is correct
17 Correct 1 ms 1624 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Runtime error 299 ms 9304 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -