fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. template <typename T>
  7. inline bool maxi(T &x, const T &val)
  8. {
  9.     if (x < val)
  10.         return x = val, true;
  11.     return false;
  12. }
  13.  
  14. template <typename T>
  15. inline bool mini(T &x, const T &val)
  16. {
  17.     if (x > val)
  18.         return x = val, true;
  19.     return false;
  20. }
  21.  
  22. const int maxn = 3010, maxk = maxn / 2, mod = 1e9 + 7;
  23. int n, k;
  24. string s;
  25. int dp[maxn][2][maxk];
  26.  
  27. inline void add(int &x, const int &val)
  28. {
  29.     if ((x += val) >= mod) x -= mod;
  30. }
  31.  
  32. int cal(int x, int type, int cur)
  33. {
  34.     if (x == n)
  35.     {
  36.         return cur == 0;
  37.     }
  38.     int &d = dp[x][type][cur];
  39.     if (d != -1)
  40.         return d;
  41.     d = 0;
  42.     if (cur < k)
  43.     {
  44.         add(d, 3ll * cal(x + 1, 0, cur + 1) % mod);
  45.     }
  46.     if (cur > 0)
  47.     {
  48.         add(d, cal(x + 1, 1, cur - 1));
  49.     }
  50.     return d;
  51. }
  52.  
  53. int calsub1(int x, int type, int cur)
  54. {
  55.     if (x == n)
  56.     {
  57.         return cur == 0;
  58.     }
  59.     int &d = dp[x][type][cur];
  60.     if (d != -1)
  61.         return d;
  62.     d = 0;
  63.     if (cur < k)
  64.     {
  65.         add(d, calsub1(x + 1, 0, cur + 1) % mod);
  66.     }
  67.     if (cur > 0)
  68.     {
  69.         add(d, cal(x + 1, 1, cur - 1));
  70.     }
  71.     return d;
  72. }
  73.  
  74. void solvesub1()
  75. {
  76.     memset(dp, -1, sizeof dp);
  77.     int res = 1;
  78.     int cur = 0;
  79.     vector<char> dak;
  80.     for (int i = 0; i < n; i++)
  81.     {
  82.         if (cur < k) {
  83.             if ('(' < s[i])
  84.             {
  85.                 add(res, calsub1(i + 1, 0, cur + 1));
  86.             }
  87.         }
  88.         if (s[i] == '(')
  89.         {
  90.             dak.push_back(s[i]);
  91.             cur++;
  92.         }
  93.         else
  94.         {
  95.             dak.pop_back();
  96.             cur--;
  97.         }
  98.     }
  99.     cout << res << '\n';
  100. }
  101.  
  102. void solve()
  103. {
  104.     int T;
  105.     cin >> T;
  106.     cin >> n >> k;
  107.     cin >> s;
  108.     if (T == 1) {
  109.         solvesub1();
  110.         return;
  111.     }
  112.     memset(dp, -1, sizeof dp);
  113.     int res = 1;
  114.     int cur = 0;
  115.     vector<char> dak;
  116.     for (int i = 0; i < n; i++)
  117.     {
  118.         if (cur < k) {
  119.             if ('(' < s[i])
  120.             {
  121.                 add(res, cal(i + 1, 0, cur + 1));
  122.             }
  123.             if ('[' < s[i])
  124.             {
  125.                 add(res, cal(i + 1, 0, cur + 1));
  126.             }
  127.             if ('{' < s[i])
  128.             {
  129.                 add(res, cal(i + 1, 0, cur + 1));
  130.             }
  131.         }
  132.         if (cur > 0) {
  133.             char c = dak.back();
  134.             if ((c == '(' && ')' < s[i])
  135.              || (c == '[' && ']' < s[i])
  136.              || (c == '{' && '}' < s[i])) {
  137.                 add(res, cal(i + 1, 1, cur - 1));
  138.              }
  139.         }
  140.         if (s[i] == '(' || s[i] == '[' || s[i] == '{')
  141.         {
  142.             dak.push_back(s[i]);
  143.             cur++;
  144.         }
  145.         else
  146.         {
  147.             dak.pop_back();
  148.             cur--;
  149.         }
  150.     }
  151.     cout << res << '\n';
  152. }
  153.  
  154. signed main()
  155. {
  156. 	#ifndef ONLINE_JUDGE
  157. 	freopen("test.inp","r",stdin);
  158. 	freopen("test.out","w",stdout);
  159. 	#endif
  160. 	solve();
  161. }
  162.  
Success #stdin #stdout 0.02s 74368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/jaCyv0
language:
C++14 (gcc 8.3)
created:
109 days 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!