fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define pii pair<int,int>
  6. #define int long long 
  7. const int N=100,mod=1e9+7;  
  8. int t,n,k;
  9. string s;
  10. char x[10]={'(',')','[',']','{','}'};
  11. int pos[260];
  12. string dp[N+2][N/2];
  13. string add(string x,string y)
  14. {
  15.   if (x.size()<y.size()) 
  16.   {
  17.     reverse(x.begin(),x.end());
  18.     while (x.size()<y.size()) x+="0";
  19.     reverse(x.begin(),x.end());
  20.   }
  21.   if (x.size()>y.size()) 
  22.   {
  23.     reverse(y.begin(),y.end());
  24.     while (x.size()>y.size()) y+="0";
  25.     reverse(y.begin(),y.end());
  26.   }
  27.   string c="";
  28.   int nho=0;
  29.   for (int i=x.size()-1;i>=0;i--)
  30.   {
  31.     int d=x[i]+y[i]+nho-96;
  32.     nho=d/10;d%=10;
  33.     c+=char(d+48);
  34.   }
  35.   if (nho>0) c+=char(nho+48);
  36.   reverse(c.begin(),c.end());
  37.   return c;
  38. }
  39. string cal(int i,int j)
  40. {
  41.   if (dp[i][j]!="-1") return dp[i][j];
  42.   if (i==n) 
  43.   {
  44.     string st="";
  45.     st+=char((j==0)+'0');
  46.     return st;
  47.   }
  48.   string &res=dp[i][j];
  49.   res="0";
  50.   if (j<k) 
  51.   for (int p=1;p<=3;p++) res=add(res,cal(i+1,j+1));
  52.   if (j>0) res=add(res,cal(i+1,j-1));
  53.   return res;
  54. }
  55. void Sol2()
  56. {
  57.   for (int i=0;i<=n;i++)
  58.   for (int j=0;j<=k;j++) dp[i][j]="-1";
  59.   vector<char> g;
  60.   string res="1";
  61.   int d=0;
  62.   for (int i=0;i<s.size();i++)
  63.   {
  64.     if (d<k)
  65.     {
  66.       for (int j=0;j<6;j+=2)
  67.       if (x[j]<s[i]) res=add(res,cal(i+1,d+1));
  68.     }
  69.     if (d>0)
  70.     if (x[pos[g.back()]+1]<s[i])
  71.     res=add(res,cal(i+1,d-1));
  72.     if (pos[s[i]]%2==0) g.push_back(s[i]),d++;
  73.     else g.pop_back(),d--;
  74.   }
  75.   cout<<res<<"\n";
  76. }
  77. signed main() 
  78. {
  79.   ios_base::sync_with_stdio(0);
  80.   cin.tie(0);cout.tie(0);
  81.   if (fopen("BTN.inp","r"))
  82.   {
  83.     freopen("BTN.inp","r",stdin);
  84.     freopen("BTN.out","w",stdout);
  85.   }
  86.   pos['(']=0;pos[')']=1;
  87.   pos['[']=2;pos[']']=3;
  88.   pos['{']=4;pos['}']=5;
  89.   cin>>t>>n>>k;
  90.   cin>>s;
  91.   Sol2();
  92. }
  93.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
2
8 4
{}(({}))
stdout
copy 
1008
https://ideone.com/ZQRPjv
language:
C++14 (gcc 8.3)
created:
14 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!