fork(1) download
copy 
  1. // author : Nguyễn Trọng Nguyễn - ITK22 NBK
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ii pair <int, int>
  7. #define fi first
  8. #define sc second
  9.  
  10. const int maxn = 3000;
  11. const int inf = (int)1e9;
  12. const int mod = (int)1e9 + 7;
  13.  
  14. int t, n, k;
  15. char a[maxn + 5];
  16. ll dp[maxn + 5][2][maxn / 2 + 5];
  17.  
  18. char s[6] = {'(', ')', '[', ']', '{', '}'};
  19. ll rnk = 1;
  20. stack <char> st;
  21.  
  22. void add (ll &a, ll b) {
  23. 	a += b;
  24. 	if (a >= mod) a -= mod;
  25. }
  26.  
  27. void init () {
  28. 	cin >> t >> n >> k;
  29. 	for (int i = 0; i < n; i++)
  30. 		cin >> a[i];
  31. }
  32.  
  33. ll calc (int id, bool f, int len, bool ok) {
  34. 	if (len < 0 or len > k) return 0;
  35. 	if (id == n) return len == 0;
  36.  
  37. 	if (dp[id][f][len] != -1) return dp[id][f][len];
  38.  
  39. 	ll res = 0;
  40. 	int mx = ok == 1 ? 6 : 2;
  41. 	for (int i = 0; i < mx; i++) {
  42. 		if (i & 1) {
  43. 			if (len == 0 or st.top() != s[i - 1]) continue;
  44. 			st.pop();
  45. 			add(res, calc(id + 1, 1, len - 1, 1));
  46. 			st.push(s[i - 1]);
  47. 		}
  48. 		else {
  49. 			st.push(s[i]);
  50. 			add(res, calc(id + 1, 0, len + 1, ok));
  51. 			st.pop();
  52. 		}
  53. 	}
  54.  
  55. 	return dp[id][f][len] = res;
  56. }
  57.  
  58. void getrank (int id = 0, int len = 0) {
  59. 	if (id == n or len < 0 or len > k) return ;
  60.  
  61. 	int mx = t == 1 ? 2 : 6;
  62. 	for (int i = 0; i < mx; i++) {
  63. 		if (i & 1) {
  64. 			if (len == 0 or st.top() != s[i - 1]) continue;
  65. 			st.pop();
  66. 			if (a[id] != s[i]) add(rnk, calc(id + 1, 1, len - 1, 1));
  67. 			else {
  68. 				getrank(id + 1, len - 1);
  69. 				return ;
  70. 			}
  71. 			st.push(s[i - 1]);
  72. 		}
  73. 		else {
  74. 			st.push(s[i]);
  75. 			if (a[id] != s[i]) add(rnk, calc(id + 1, 0, len + 1, t == 2));
  76. 			else {
  77. 				getrank(id + 1, len + 1);
  78. 				return ;
  79. 			}
  80. 			st.pop();	
  81. 		}
  82. 	}
  83. }
  84.  
  85. void process () {
  86. 	memset(dp, -1, sizeof dp);
  87. 	getrank();
  88. 	cout << rnk;
  89. }
  90.  
  91. signed main () {
  92. 	cin.tie(0)->sync_with_stdio(false);
  93.  
  94. 	#ifndef ONLINE_JUDGE
  95. 	freopen("test.inp","r",stdin);
  96. 	freopen("test.out","w",stdout);
  97. 	#endif
  98.  
  99. 	init();
  100. 	process();
  101.  
  102. 	return 0;
  103. }
  104.  
Success #stdin #stdout 0.02s 74204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/oINdE4
language:
C++14 (gcc 8.3)
created:
100 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!