fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 3e3;
  9. const int maxk = maxn >> 1;
  10. const int MOD = 1e9 + 7;
  11.  
  12. int t, n, k, level = 0;
  13. string s;
  14. ll dp[maxn + 10][maxk + 10], ans = 1;
  15. vector<char> stk;
  16.  
  17. void add(ll &a, ll b)
  18. {
  19.     a += b;
  20.     if (a >= MOD)
  21.         a -= MOD;
  22. }
  23. bool is_open(char c)
  24. {
  25.     return c == '(' || c == '[' || c == '{';
  26. }
  27. int trans(char c)
  28. {
  29.     if (t == 1 && c != ')')
  30.         return 0;
  31.     if (c == '(')
  32.         return 0;
  33.     if (c == '[' || c == ')')
  34.         return 1;
  35.     if (c == '{' || c == ']')
  36.         return 2;
  37.     return 3;
  38. }
  39. char inver(char c)
  40. {
  41.     if (c == '(')
  42.         return ')';
  43.     if (c == '[')
  44.         return ']';
  45.     return '}';
  46. }
  47.  
  48. int main()
  49. {
  50.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  51.     if (fopen("BIEUTHUCNGOAC.INP", "r"))
  52.     {
  53.         freopen("BIEUTHUCNGOAC.INP", "r", stdin);
  54.         freopen("BIEUTHUCNGOAC.OUT", "w", stdout);
  55.     }
  56.  
  57.     cin >> t >> n >> k >> s;
  58.     s = ' ' + s;
  59.     dp[0][0] = 1;
  60.     for (int i = 0; i < n; i++)
  61.         for (int j = 0; j <= k; j++)
  62.         {
  63.             if (j < k)
  64.                 add(dp[i + 1][j + 1], dp[i][j]);
  65.             if (j)
  66.             {
  67.                 add(dp[i + 1][j - 1], dp[i][j]);
  68.                 if (t == 2)
  69.                 {
  70.                     add(dp[i + 1][j - 1], dp[i][j]);
  71.                     add(dp[i + 1][j - 1], dp[i][j]);
  72.                 }
  73.             }
  74.         }
  75. //    for (int i = 1; i <= n; i++)
  76. //    {
  77. //        for (int j = 0; j <= k; j++)
  78. //            cout << dp[i][j] << ' ';
  79. //        el;
  80. //    }
  81.     for (int i = 1; i <= n; i++)
  82.     {
  83.         if (is_open(s[i]))
  84.         {
  85.             level++;
  86.             add(ans, trans(s[i]) * dp[n - i][level] % MOD);
  87.             if (stk.size() && s[i] > inver(stk.back()) && level >= 2)
  88.                 add(ans, dp[n - i][level - 2]);
  89.             stk.push_back(s[i]);
  90.         }
  91.         else
  92.         {
  93.             if (level < k)
  94.                 add(ans, trans(s[i]) * dp[n - i][level + 1] % MOD);
  95.             level--;
  96.             stk.pop_back();
  97.         }
  98.  
  99.     }
  100.  
  101.     cout << ans;
  102. }
  103.  
  104.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/CaL5Qs
language:
C++14 (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!