fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. class BracketSequenceDiv1 {
  7. public:
  8. int n;
  9. string s;
  10. typedef long long LL;
  11. LL memo[41][41][41][4];
  12.  
  13. LL f(int p, int Lr, int Ls, int last)
  14. {
  15. 	if (p == n)
  16. 		return Lr == 0 && Ls == 0 && last != 3;
  17.  
  18. 	LL& res = memo[p][Lr][Ls][last];
  19. 	if (res != -1LL)
  20. 		return res;
  21. 	res = 0;
  22. 	if (s[p] == '(')
  23. 	{
  24. 		res = f(p+1, Lr+1, Ls, 0)+f(p+1, Lr, Ls, last);
  25. 	}
  26. 	else if (s[p] == '[')
  27. 	{
  28. 		res = f(p+1, Lr, Ls+1, 1)+f(p+1, Lr, Ls, last);
  29. 	}
  30. 	else if (s[p] == ')')
  31. 	{
  32. 		if (Lr == 0 && Ls == 0)
  33. 			res = f(p+1, Lr, Ls, last);
  34. 		else if (Lr > 0 && Ls == 0)
  35. 			res = f(p+1, Lr, Ls, last)+f(p+1, Lr-1, Ls, Lr-1?0:2);
  36. 		else if (Lr == 0 && Ls > 0)
  37. 			res = f(p+1, Lr, Ls, last);
  38. 		else // Lr > 0 && Ls > 0
  39. 		{
  40. 			res = f(p+1, Lr, Ls, last);
  41. 			if (last != 1)
  42. 				res += f(p+1, Lr-1, Ls, Lr-1?0:1);
  43. 		}
  44. 	}
  45. 	else // s[p] == ']'
  46. 	{
  47. 		if (Lr == 0 && Ls == 0)
  48. 			res = f(p+1, Lr, Ls, last);
  49. 		else if (Lr > 0 && Ls == 0)
  50. 			res = f(p+1, Lr, Ls, last);
  51. 		else if (Lr == 0 && Ls > 0)
  52. 			res = f(p+1, Lr, Ls, last)+f(p+1, Lr, Ls-1, Ls-1?1:2);
  53. 		else
  54. 		{
  55. 			res = f(p+1, Lr, Ls, last);
  56. 			if (last != 0)
  57. 				res += f(p+1, Lr, Ls-1, Ls-1?1:0);
  58. 		}
  59. 	}
  60. 	return res;
  61. }
  62.  
  63. long long count(string s_) 
  64. {
  65. 	s = s_;
  66. 	n = s.size();	
  67. 	memset(memo, -1, sizeof(memo));
  68.  
  69. 	return f(0, 0, 0, 3);
  70. }
  71. };
  72.  
  73.  
  74. <%:testing-code%>
  75. //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:74:1: error: expected unqualified-id before '<%' token
 <%:testing-code%>
 ^
stdout
copy 
Standard output is empty
https://ideone.com/m79V8Y
language:
C++ (gcc 8.3)
created:
8 years 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!