Source code for submission s578

fq.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <queue>
  11.  
  12. using namespace std;
  13.  
  14. int main(){
  15.   string vstup;
  16.   while(cin>>vstup){
  17.  
  18.     vector<vector<long long> > dynamika; 
  19.  
  20.     dynamika.resize(vstup.size()+1, vector<long long> (vstup.size()+3, 0));
  21.  
  22.     dynamika[vstup.size()][0] = 1;
  23.  
  24.     for(int i = vstup.size() -1; i>=0; i--){
  25.       if(vstup[i]!='('){
  26. 	for(int j = 0; j < vstup.size()+2; j++){
  27. 	 dynamika[i][j+1]+= dynamika[i+1][j];
  28. 	 dynamika[i][j+1]%=1000000;
  29. 	}	
  30.       }
  31.  
  32.       if(vstup[i]!=')'){
  33. 	for(int j = 1; j < vstup.size()+3; j++){
  34. 	 dynamika[i][j-1]+= dynamika[i+1][j];
  35. 	 dynamika[i][j-1]%=1000000;
  36. 	}	
  37.       }
  38.     }
  39.  
  40.     cout<<dynamika[0][0]<<endl;
  41.   }
  42.  
  43. }