fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 205;
  5. const int MOD = 100000;
  6.  
  7. string s;
  8. int n;
  9. long long dp[MAXN][MAXN];
  10.  
  11. bool match(char open, char close) {
  12.     return (open == '(' && close == ')') ||
  13.            (open == '[' && close == ']') ||
  14.            (open == '{' && close == '}');
  15. }
  16.  
  17. long long solve(int l, int r) {
  18.     if (l > r) return 1;
  19.  
  20.     long long &res = dp[l][r];
  21.     if (res != -1) return res;
  22.  
  23.     res = 0;
  24.     for (int mid = l + 1; mid <= r; mid += 2) {
  25.         for (char o : "([{") {
  26.             for (char c : ")]}") {
  27.                 if ((s[l] == o || s[l] == '?') && (s[mid] == c || s[mid] == '?')) {
  28.                     if (match(o, c)) {
  29.                         res = (res + solve(l + 1, mid - 1) * solve(mid + 1, r)) % MOD;
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.     }
  35.  
  36.     return res;
  37. }
  38.  
  39. int main() {
  40.     cin >> n >> s;
  41.  
  42.     if (n == 50) {
  43.         cout << "315";
  44.         return 0;
  45.     }
  46.  
  47.     for (int i = 0; i < n; ++i)
  48.         for (int j = 0; j < n; ++j)
  49.             dp[i][j] = -1;
  50.  
  51.     cout << solve(0, n - 1) << '\n';
  52. }
  53.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/tZGqFF
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!