Advertisement
Galebickosikasa

Untitled

Aug 10th, 2020
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.33 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
  3. // #pragma comment(linker, "/stack:200000000"]
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <bitset>
  16. #include <stack>
  17. #include <random>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define ll long long
  26. #define ld long double
  27. #define hm unordered_map
  28. #define pii pair<int, int>
  29. #define sz(a) (int)a.size()
  30. #define all(a) a.begin(), a.end()
  31. #define cinv(v) for (auto& x: v) cin >> x
  32. #define fr(i, n) for (int i = 0; i < n; ++i)
  33. #define fl(i, l, n) for (int i = l; i < n; ++i)
  34.  
  35. // #define int ll
  36.  
  37. using namespace std;
  38.  
  39. #ifdef __LOCAL
  40. #define dbg(x) cerr << #x << " : " << x << '\n'
  41. const int maxn = 20;
  42. #else
  43. #define dbg(x)
  44. const int maxn = 2000 + 20;
  45. #endif
  46.  
  47. //tg: @galebickosikasa
  48.  
  49. ostream& operator << (ostream& out, vector<int>& v) {
  50. for (auto& x: v) out << x << ' ';
  51. return out;
  52. }
  53.  
  54. ostream& operator << (ostream& out, pii& v) {
  55. out << v.fi << ", " << v.se;
  56. return out;
  57. }
  58.  
  59. istream& operator >> (istream& in, pii& a) {
  60. in >> a.fi >> a.se;
  61. return in;
  62. }
  63.  
  64. const ll inf = (ll) 2e9;
  65. const ld pi = asin (1) * 2;
  66. const ld eps = 1e-8;
  67. const ll mod = (ll)1e9 + 7;
  68. const ll ns = 97;
  69.  
  70. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  71.  
  72. int dp1[maxn][maxn], dp2[maxn][maxn], dp3[maxn][maxn], dp4[maxn][maxn], dp5[maxn][maxn], dp6[maxn][maxn], dp7[maxn][maxn], dp8[maxn][maxn],
  73. dp[maxn][maxn], n, m;
  74. char g[maxn][maxn];
  75.  
  76. void get1 (int i) {
  77. dp1[i][m - 1] = 1;
  78. for (int j = m - 2; j >= 0; --j) {
  79. if (g[i][j + 1] == g[i][j]) dp1[i][j] = dp1[i][j + 1] + 1;
  80. else dp1[i][j] = 1;
  81. }
  82. }
  83.  
  84. void get2 (int i) {
  85. dp2[i][0] = 1;
  86. for (int j = 1; j < m; ++j) {
  87. if (g[i][j - 1] == g[i][j]) dp2[i][j] = dp2[i][j - 1] + 1;
  88. else dp2[i][j] = 1;
  89. }
  90. }
  91.  
  92. void get3 (int j) {
  93. dp3[0][j] = 1;
  94. for (int i = 1; i < n; ++i) {
  95. if (g[i - 1][j] == g[i][j]) dp3[i][j] = dp3[i - 1][j] + 1;
  96. else dp3[i][j] = 1;
  97. }
  98. }
  99.  
  100. void get4 (int j) {
  101. dp4[n - 1][j] = 1;
  102. for (int i = n - 2; i >= 0; --i) {
  103. if (g[i + 1][j] == g[i][j]) dp4[i][j] = dp4[i + 1][j] + 1;
  104. else dp4[i][j] = 1;
  105. }
  106. }
  107.  
  108. void get5 (int i, int j) {
  109. dp5[i][j] = 1;
  110. fl (k, 1, inf) {
  111. if (i + k >= n || j - k < 0) break;
  112. if (g[i + k - 1][j - k + 1] == g[i + k][j - k]) dp5[i + k][j - k] = dp5[i + k - 1][j - k + 1] + 1;
  113. else dp5[i + k][j - k] = 1;
  114. }
  115. }
  116.  
  117. void get6 (int i, int j) {
  118. dp6[i][j] = 1;
  119. fl (k, 1, inf) {
  120. if (i - k < 0 || j + k >= m) break;
  121. if (g[i - k + 1][j + k - 1] == g[i - k][j + k]) dp6[i - k][j + k] = dp6[i - k + 1][j + k - 1] + 1;
  122. else dp6[i - k][j + k] = 1;
  123. }
  124. }
  125.  
  126. void get7 (int i, int j) {
  127. dp7[i][j] = 1;
  128. fl (k, 1, inf) {
  129. if (i + k >= n || j + k >= m) break;
  130. if (g[i + k - 1][j + k - 1] == g[i + k][j + k]) dp7[i + k][j + k] = dp7[i + k - 1][j + k - 1] + 1;
  131. else dp7[i + k][j + k] = 1;
  132. }
  133. }
  134.  
  135. void get8 (int i, int j) {
  136. dp8[i][j] = 1;
  137. fl (k, 1, inf) {
  138. if (i - k < 0 || j - k < 0) break;
  139. if (g[i - k + 1][j - k + 1] == g[i - k][j - k]) dp8[i - k][j - k] = dp8[i - k + 1][j - k + 1] + 1;
  140. else dp8[i - k][j - k] = 1;
  141. }
  142. }
  143.  
  144. void solve () {
  145. cin >> n >> m;
  146. fr (i, n) fr (j, m) cin >> g[i][j];
  147. fr (i, n) {
  148. get1 (i);
  149. get2 (i);
  150. get5 (i, m - 1);
  151. get6 (i, 0);
  152. get7 (i, 0);
  153. get8 (i, m - 1);
  154. }
  155. fr (j, m) {
  156. get3 (j);
  157. get4 (j);
  158. get5 (0, j);
  159. get6 (n - 1, j);
  160. get7 (0, j);
  161. get8 (n - 1, j);
  162. }
  163. // fr (i, n) fr (j, m) dbg (g[i][j]);
  164. fr (i, n) fr (j, m) dp[i][j] = min (min (min (dp1[i][j], dp2[i][j]), min (dp3[i][j], dp4[i][j])), min (min (dp5[i][j], dp6[i][j]), min (dp7[i][j], dp8[i][j])));
  165. int ans = 0;
  166. fr (i, n) fr (j, m) {
  167. dbg (i);
  168. dbg (j);
  169. dbg (dp[i][j]);
  170. dbg (dp1[i][j]);
  171. dbg (dp2[i][j]);
  172. dbg (dp3[i][j]);
  173. dbg (dp4[i][j]);
  174. dbg (dp5[i][j]);
  175. dbg (dp6[i][j]);
  176. dbg (dp7[i][j]);
  177. dbg (dp8[i][j]);
  178. ans += dp[i][j];
  179. }
  180. cout << ans << '\n';
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188. }
  189.  
  190.  
  191.  
  192.  
  193. signed main () {
  194. ios_base::sync_with_stdio(false);
  195. cin.tie(nullptr);
  196. cout.tie(nullptr);
  197. int q = 1;
  198. // cin >> q;
  199. while (q--) solve ();
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement