fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>
  3. #include <unordered_set>
  4. #include <random>
  5. #ifdef _MSC_VER
  6. #	include <intrin.h>
  7. #	define __builtin_popcount __popcnt
  8. #endif
  9.  
  10. //#include <atcoder/all>
  11. //using namespace atcoder;
  12. //typedef modint998244353 mint;
  13.  
  14. using namespace std;
  15.  
  16. typedef long long int lld;
  17. typedef long double ld;
  18. typedef pair<int, int> pii;
  19. typedef pair<lld, lld> pll;
  20. typedef vector<int> vi;
  21. typedef vector<lld> vl;
  22. typedef vector<ld> vld;
  23. typedef vector<char> vch;
  24. typedef vector<string> vs;
  25. typedef vector<bool> vb;
  26. typedef vector<double> vd;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29. typedef vector<vi> vivi;
  30. typedef vector<vl> vlvl;
  31. typedef vector<vch> vcvc;
  32. typedef vector<vb> vbvb;
  33. typedef vector<vs> vsvs;
  34.  
  35. const lld mod = 1000000007LL;
  36. const int inf = 1LL << 29;
  37. const int nom = 1000000;
  38.  
  39. vivi moves = { {0, -1}, {-1, 0}, {1, 0}, {0, 1}};
  40.  
  41. bool isgo(int n, int x, int y)
  42. {
  43. 	return x >= 0 && x < n && y >= 0 && y < n;
  44. }
  45.  
  46. int op(vivi &vc, int n, int k, int &mx)
  47. {
  48. 	int tp, tp2, tp3, tp4, tp5, tp6, tp7, ok = 0;
  49.  
  50. 	for (int i = 0; i < n; ++i)
  51. 	{
  52. 		if (k == 0)
  53. 			tp = tp5 = i, tp2 = tp6 = 0;
  54. 		else if (k == 1)
  55. 			tp = tp5 = 0, tp2 = tp6 = i;
  56. 		else if (k == 2)
  57. 			tp = tp5 = n - 1, tp2 = tp6 = i;
  58. 		else
  59. 			tp = tp5 = i, tp2 = tp6 = n - 1;
  60.  
  61. 		while (1)
  62. 		{
  63. 			while (isgo(n, tp, tp2) && !vc[tp][tp2])
  64. 				tp += moves[3 - k][0], tp2 += moves[3 - k][1];
  65.  
  66. 			if (!isgo(n, tp, tp2))
  67. 				break;
  68.  
  69. 			if (k == 0)
  70. 				tp3 = i, tp4 = tp2 + 1;
  71. 			else if (k == 1)
  72. 				tp3 = tp + 1, tp4 = i;
  73. 			else if (k == 2)
  74. 				tp3 = tp - 1, tp4 = i;
  75. 			else
  76. 				tp3 = i, tp4 = tp2 - 1;
  77.  
  78. 			while (isgo(n, tp3, tp4) && !vc[tp3][tp4])
  79. 				tp3 += moves[3 - k][0], tp4 += moves[3 - k][1];
  80.  
  81. 			if (!isgo(n, tp3, tp4))
  82. 				break;
  83.  
  84. 			if (vc[tp][tp2] == vc[tp3][tp4])
  85. 			{
  86. 				tp7 = vc[tp][tp2] * 2;
  87. 				vc[tp][tp2] = vc[tp3][tp4] = 0;
  88. 				vc[tp5][tp6] = tp7;
  89.  
  90. 				ok = 1;
  91. 				mx = max(mx, vc[tp5][tp6]);
  92. 			}
  93. 			else
  94. 			{
  95. 				if (tp != tp5 || tp2 != tp6)
  96. 					ok = 1;
  97.  
  98. 				tp7 = vc[tp][tp2];
  99. 				vc[tp][tp2] = 0;
  100. 				vc[tp5][tp6] = tp7;
  101.  
  102. 				mx = max(mx, vc[tp5][tp6]);
  103. 			}
  104.  
  105. 			tp = tp3, tp2 = tp4;
  106. 			tp5 += moves[3 - k][0], tp6 += moves[3 - k][1];
  107. 		}
  108.  
  109. 		if (isgo(n, tp, tp2) && vc[tp][tp2])
  110. 		{
  111. 			if (tp != tp5 || tp2 != tp6)
  112. 				ok = 1;
  113.  
  114. 			tp7 = vc[tp][tp2];
  115. 			vc[tp][tp2] = 0;
  116. 			vc[tp5][tp6] = tp7;
  117.  
  118. 			mx = max(mx, vc[tp5][tp6]);
  119. 		}
  120. 	}
  121.  
  122. 	return ok;
  123. }
  124.  
  125. int go(vivi &vc, int n, int now, int last_dir, int initmx, int best)
  126. {
  127. 	int nowmx, tp, finmx = best;
  128. 	vivi tmp;
  129.  
  130. 	if (now == 10)
  131. 		return finmx;
  132.  
  133. 	for (int k = 0; k < 4; ++k)
  134. 	{
  135. 		nowmx = initmx;
  136. 		tmp = vc;
  137. 		tp = op(tmp, n, k, nowmx);
  138.  
  139. 		if (tp && (nowmx << (10 - (now + 1))) > finmx)
  140. 			finmx = max(finmx, go(tmp, n, now + 1, k, nowmx, max(nowmx, finmx)));
  141. 	}
  142.  
  143. 	return finmx;
  144. }
  145.  
  146. int main()
  147. {
  148. 	cin.tie(NULL), cout.tie(NULL);
  149. 	ios::sync_with_stdio(false);
  150.  
  151. 	int n, finmx, initmx = 0, nowmx;
  152.  
  153. 	cin >> n;
  154.  
  155. 	vivi vc(n, vi(n)), tmp;
  156.  
  157. 	for (int i = 0; i < n; ++i)
  158. 	{
  159. 		for (int j = 0; j < n; ++j)
  160. 		{
  161. 			cin >> vc[i][j];
  162.  
  163. 			initmx = max(initmx, vc[i][j]);
  164. 		}
  165. 	}
  166.  
  167. 	finmx = initmx;
  168.  
  169. 	for (int k = 0; k < 4; ++k)
  170. 	{
  171. 		nowmx = initmx;
  172.  
  173. 		if ((nowmx << 10) > finmx)
  174. 			finmx = max(finmx, go(vc, n, 0, k, nowmx, finmx));
  175. 	}
  176.  
  177. 	cout << finmx;
  178.  
  179. 	cout << '\n';
  180.  
  181. 	return 0;
  182. }
Success #stdin #stdout 0.75s 5304KB
comments (?)
stdin
copy 
20
64 64 32 16 256 0 32 0 512 0 0 128 0 0 0 128 16 64 16 0
16 16 64 0 0 128 64 0 0 0 8 0 256 0 512 128 32 0 16 32
0 128 0 0 0 32 32 64 0 0 0 0 0 32 16 64 0 16 0 0
0 0 0 128 0 128 512 0 0 32 256 32 64 0 32 0 64 0 0 0
0 0 0 16 0 16 0 0 32 0 32 0 0 0 64 0 64 64 0 64
16 0 64 32 128 64 0 128 16 0 0 0 64 0 0 128 0 64 0 128
0 64 32 64 64 0 0 0 128 0 0 0 512 32 0 64 0 0 64 0
0 0 0 0 0 8 256 0 0 32 0 0 0 0 0 8 128 16 0 64
0 8 0 16 0 0 0 128 0 16 16 0 32 0 0 0 0 64 128 128
0 16 16 32 64 0 64 256 0 16 128 128 0 0 64 0 16 0 0 0
0 0 0 16 0 0 0 0 32 0 8 16 128 64 256 0 32 16 128 0
0 256 16 256 0 16 32 8 128 64 0 32 32 512 0 16 0 8 16 0
64 8 16 0 0 0 0 0 128 64 0 128 0 0 8 0 16 0 0 0
0 0 0 0 32 64 0 8 0 0 32 0 0 0 16 128 256 0 128 0
64 8 0 16 32 0 0 0 8 64 64 0 0 0 0 256 64 0 16 0
0 0 32 0 32 32 8 0 0 0 64 0 32 0 0 16 64 128 0 32
0 0 8 64 0 64 0 0 128 64 64 0 0 0 0 32 128 0 128 16
0 0 0 0 32 0 0 32 32 0 16 0 128 0 0 0 0 256 0 32
16 256 0 64 0 16 0 64 0 32 64 32 0 0 0 64 32 64 0 0
16 8 0 32 64 256 0 0 0 128 8 0 32 0 64 0 0 0 64 128
stdout
copy 
4096
https://ideone.com/F208wl
language:
C++ (gcc 8.3)
created:
34 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!