SHARE
TWEET

Untitled

a guest Feb 20th, 2016 141 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define endl "\n"
  3. using namespace std;
  4.  
  5. const int MOD = 1000000007;
  6.  
  7. int n,m,k;
  8. char a[1<<17];
  9. bool vis[2044][5111][2];
  10. int dp_ans[2044][5111][2];
  11. int s[1<<17],min_s;
  12.  
  13. int get_dp(int pos, int sum, bool f) {
  14.     if(sum>2000 || sum<0) return 0;
  15.     if(pos>k) {
  16.         if(f==false) {
  17.             if(sum+min_s>=0 && sum+s[m]==0) return 1;
  18.             else return 0;
  19.         }
  20.         else {
  21.             if(sum==0) return 1;
  22.             else return 0;
  23.         }
  24.     }
  25.     if(vis[pos][sum][f]) return dp_ans[pos][sum][f];
  26.     int ans=0;
  27.     ans=(ans+get_dp(pos+1,sum+1,f))%MOD;//Open
  28.     ans=(ans+get_dp(pos+1,sum-1,f))%MOD;//Close
  29.     if(f==false) {
  30.         if(sum+min_s>=0) ans=(ans+get_dp(pos,sum+s[m],1))%MOD;//Skip;
  31.     }
  32.     vis[pos][sum][f]=true;
  33.     dp_ans[pos][sum][f]=ans;
  34.     return ans;
  35. }
  36.  
  37. int main() {
  38.     cin.tie(NULL);
  39.     ios::sync_with_stdio(0);
  40.     int i;
  41.    
  42.     cin>>n>>m;
  43.     k=n-m;
  44.     cin>>(a+1);
  45.     for(i=1;i<=m;i++) if(a[i]=='(') s[i]=1; else s[i]=-1;
  46.     for(i=1;i<=m;i++) s[i]+=s[i-1];
  47.     min_s=1000000000;
  48.     for(i=1;i<=m;i++) min_s=min(min_s,s[i]);
  49.     cout<<get_dp(1,0,0)<<endl;
  50.    
  51.     return 0;
  52. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top