fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28.  
  29.  
  30. string a;
  31.  
  32. //* Pivot 1st palindrome substring
  33.  
  34. int consistency1(int n){
  35.  
  36. 	vector<vector<bool>> dp(n, vector<bool>(n, false));
  37. 	vector<vector<int>> dpCt(n, vector<int>(n, 0));
  38.  
  39. 	for(int gap=0; gap<n; gap++){
  40. 		for(int i=0, j=gap; j<n; i++, j++){
  41. 			if(gap == 0){
  42. 				dp[i][j] = true;
  43. 				dpCt[i][j] = 1;
  44. 			}
  45. 			else if(gap == 1){
  46. 				if(a[i] == a[j]){
  47. 					dp[i][j] = true;
  48. 					dpCt[i][j] = 3;
  49. 				}
  50. 				else{
  51. 					dpCt[i][j] = 2;
  52. 				}
  53. 			}
  54. 			else{
  55. 				dpCt[i][j] = dpCt[i][j-1] + dpCt[i+1][j] - dpCt[i+1][j-1];
  56. 				if(a[i] == a[j] && dp[i+1][j-1]){
  57. 					dp[i][j] = true;
  58. 					dpCt[i][j]++;
  59. 				}
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	int ans = 0;
  65. 	for(int i=0; i<=n-3; i++){
  66. 		int x = 0;
  67.  
  68. 		int j = i;
  69. 		while(j>=0){
  70. 			if(dp[j][i]) x++;
  71. 			j--;
  72. 		}
  73.  
  74. 		int y = 0;
  75. 		for(int j=i+1; j<=n-2; j++){
  76. 			int p = 0;
  77.  
  78. 			int k = j;
  79. 			while(k>i){
  80. 				if(dp[k][j]) p++;
  81. 				k--;
  82. 			}
  83. 			int q = dpCt[j+1][n-1];
  84.  
  85. 			y += p*q;
  86. 		}
  87.  
  88. 		ans += x*y;
  89. 	}
  90.  
  91.     return ans;
  92. }
  93.  
  94.  
  95.  
  96.  
  97. //* Pivot middle palindrome substring
  98.  
  99. int consistency3(int n){
  100.  
  101. 	vector<vector<bool>> dp(n, vector<bool>(n, false));
  102. 	vector<vector<int>> dpCt(n, vector<int>(n, 0));
  103. 	vector<int> dp2(n, 0);
  104.  
  105. 	for(int gap=0; gap<n; gap++){
  106. 		for(int i=0, j=gap; j<n; i++, j++){
  107. 			if(gap == 0){
  108. 				dp[i][j] = true;
  109. 				dpCt[i][j] = 1;
  110. 				dp2[j] += 1;
  111. 			}
  112. 			else if(gap == 1){
  113. 				if(a[i] == a[j]){
  114. 					dp[i][j] = true;
  115. 					dpCt[i][j] = 3;
  116. 					dp2[j] += 1;
  117. 				}
  118. 				else{
  119. 					dpCt[i][j] = 2;
  120. 				}
  121. 			}
  122. 			else{
  123. 				dpCt[i][j] = dpCt[i][j-1] + dpCt[i+1][j] - dpCt[i+1][j-1];
  124. 				if(a[i] == a[j] && dp[i+1][j-1]){
  125. 					dp[i][j] = true;
  126. 					dpCt[i][j]++;
  127. 					dp2[j]++;
  128. 				}
  129. 			}
  130. 		}
  131. 	}
  132.  
  133. 	int ans = 0;
  134. 	for(int i=0; i<=n-3; i++){
  135. 		int x = dp2[i];
  136.  
  137. 		int y = 0;
  138. 		for(int j=i+1; j<=n-2; j++){
  139.  
  140. 			int p = dp2[j];
  141. 			int q = dpCt[j+1][n-1];
  142.  
  143. 			y += p*q;
  144. 		}
  145.  
  146. 		ans += x*y;
  147. 	}
  148.  
  149.     return ans;
  150. }
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157. int consistency2(int n){
  158.  
  159. 	vector<vector<bool>> dp(n, vector<bool>(n, false));
  160. 	vector<vector<int>> dpCt(n, vector<int>(n, 0));
  161. 	vector<int> dp2(n, 0);
  162.  
  163. 	for(int gap=0; gap<n; gap++){
  164. 		for(int i=0, j=gap; j<n; i++, j++){
  165. 			if(gap == 0){
  166. 				dp[i][j] = true;
  167. 				dpCt[i][j] = 1;
  168. 				dp2[j] += 1;
  169. 			}
  170. 			else if(gap == 1){
  171. 				if(a[i] == a[j]){
  172. 					dp[i][j] = true;
  173. 					dpCt[i][j] = 3;
  174. 					dp2[j] += 1;
  175. 				}
  176. 				else{
  177. 					dpCt[i][j] = 2;
  178. 				}
  179. 			}
  180. 			else{
  181. 				dpCt[i][j] = dpCt[i][j-1] + dpCt[i+1][j] - dpCt[i+1][j-1];
  182. 				if(a[i] == a[j] && dp[i+1][j-1]){
  183. 					dp[i][j] = true;
  184. 					dpCt[i][j]++;
  185. 					dp2[j]++;
  186. 				}
  187. 			}
  188. 		}
  189. 	}
  190.  
  191. 	int ans = 0;
  192. 	for(int j=1; j<=n-2; j++){
  193.  
  194.  
  195. 		int z = dpCt[j+1][n-1];
  196.  
  197. 		int y = 0;
  198. 		int i = j;
  199. 		while(i>=1){
  200. 			int x = dp2[i-1];
  201.  
  202. 			if(dp[i][j]){
  203. 				y++;
  204.  
  205. 				ans += x * y * z;
  206. 			}
  207. 			i--;
  208. 		}
  209. 	}
  210.  
  211.     return ans;
  212. }
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227. int practice(int n){
  228.  
  229.  
  230.     return 0;
  231. }
  232.  
  233.  
  234.  
  235.  
  236.  
  237. void solve() {
  238.  
  239.     cin >> a;
  240.     int n = a.size();
  241.     cout << consistency1(n) << " " << consistency2(n) << endl;
  242.  
  243.  
  244. }
  245.  
  246.  
  247.  
  248.  
  249.  
  250. int32_t main() {
  251.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  252.  
  253.     int t = 1;
  254.     // cin >> t;
  255.     while (t--) {
  256.         solve();
  257.     }
  258.  
  259.     return 0;
  260. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
pcbcqqcbcpsfdf
stdout
copy 
760 283
https://ideone.com/BeDu9O
language:
C++14 (gcc 8.3)
created:
1 day 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!