Source code for submission s743

fq.cpp

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <limits.h>
  8. #include <map>
  9. #include <queue>
  10. #include <vector>
  11. #include <set>
  12. #include <stack>
  13. #include <bitset>
  14. #include <string>
  15.  
  16. using namespace std;
  17.  
  18. typedef pair<int,int> ii;
  19. typedef vector<int> vi;
  20. typedef vector<ii> vii;
  21. typedef set<int> si;
  22. typedef set<ii> sii;
  23.  
  24. #define MP make_pair
  25. #define PB push_back
  26. #define REP(i,a) for ( int i = 0; i < int(a); i++)
  27. #define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++)
  28. #define FORD(i,a,b) for(int i= int(a); i>=int(b); i--)
  29.  
  30. const int INF = 1<<29;
  31. typedef long long int ll;
  32. char line[1024];
  33. int len, half;
  34. const int MOD = 1000000;
  35. int tab[1002][504];
  36.  
  37. int rec(int misto, int idx, int five){
  38. int out = 0;
  39. //printf("%d %d\n", misto, idx);
  40. if ( five > half) return 0;
  41. if ( tab[misto][idx] >= 0 )
  42. return tab[misto][idx];
  43. if ( idx >= half ) {
  44. return 1;
  45. }
  46. if ( misto >= len -1) {
  47. return idx==1 && line[misto] != '(' ;
  48. }
  49. if (line[misto] == '.' ) {
  50. if ( idx == 0 )
  51. out += rec(misto+1, idx+1, five+1);
  52. else {
  53. out += rec(misto+1, idx+1, five+1);
  54. out += rec(misto+1, idx-1, five);
  55. }
  56. }
  57. else if ( line[misto] == '(' ) {
  58. out += rec(misto+1, idx+1, five+1);
  59. }
  60. else {
  61. if ( idx == 0 ) return 0;
  62. out += rec(misto+1, idx-1, five);
  63. }
  64. tab[misto][idx] = out%MOD;
  65. return out%MOD;
  66. }
  67.  
  68. void clear(){
  69. FOR(i,0,len)
  70. FOR(j,0,half+1)
  71. tab[i][j]=-1;
  72. }
  73.  
  74. int main(){
  75. while ( scanf(" %s", line) > 0 ) {
  76. len = strlen(line);
  77. half = len/2;
  78. clear();
  79. printf("%d\n", rec(0,0,0)) ;
  80. }
  81.  
  82.  
  83.  
  84. return 0;
  85. }
  86.  
  87.