fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5. typedef long long int ll;
  6. ll t, n, m, mat[50][50], minim_rowarr[50][50][50], ans_row[50][50][50], ans_col[50][50][50], minim_colarr[50][50][50], ans[50][50][50][50], minim_ans[50][50][50][50];
  7. ll solve_row(int row, int a, int b)
  8. {
  9. 	if (ans_row[row][a][b] != -1)
  10. 		return ans_row[row][a][b];
  11. 	if (a == b)
  12. 		return 0;
  13. 	ll minim = 110000;
  14. 	for (int i = a; i <= b; i++)
  15. 		minim = min(minim, mat[row][i]);
  16. 	minim_rowarr[row][a][b] = minim;
  17. 	minim_ans[row][a][row][b] = minim;
  18. 	ll maxim = 0;
  19. 	for (int i = a; i < b; i++)
  20. 	{
  21. 		maxim = max(solve_row(row, a, i)+solve_row(row, i+1, b), maxim);
  22. 	}
  23. 	ans_row[row][a][b] = maxim+minim;
  24. 	ans[row][a][row][b] = maxim+minim;
  25. 	return (maxim+minim);
  26. }
  27.  
  28. ll solve_col(int col, int a, int b)
  29. {
  30. 	if (ans_col[col][a][b] != -1)
  31. 		return ans_col[col][a][b];
  32. 	if (a == b)
  33. 		return 0;
  34. 	ll minim = 110000;
  35. 	for (int i = a; i <= b; i++)
  36. 		minim = min(minim, mat[i][col]);
  37. 	minim_colarr[col][a][b] = minim;
  38. 	minim_ans[a][col][b][col] = minim;
  39. 	ll maxim = 0;
  40. 	for (int i = a; i < b; i++)
  41. 	{
  42. 		maxim = max(solve_col(col, a, i)+solve_col(col, i+1, b), maxim);
  43. 	}
  44. 	ans_col[col][a][b] = maxim+minim;
  45. 	ans[a][col][b][col] = maxim+minim;
  46. 	return (maxim+minim);
  47. }
  48.  
  49. int main()
  50. {
  51. 	ios::sync_with_stdio(false);
  52. 	cin>>t;
  53. 	for (int i = 1; i <= t; i++)
  54. 	{
  55. 		memset(ans_row, -1, sizeof(ans_row));
  56. 		memset(ans_col, -1, sizeof(ans_col));
  57. 		memset(ans, 0, sizeof(ans));
  58. 		memset(minim_ans, 0, sizeof(minim_ans));
  59. 		memset(minim_rowarr, 0, sizeof(minim_rowarr));
  60. 		memset(minim_colarr, 0, sizeof(minim_colarr));
  61. 		memset(mat, 0, sizeof(mat));
  62. 		cin>>n>>m;
  63. 		for (int j = 1; j <= n; j++)
  64. 		{
  65. 			for (int k = 1; k <= m; k++)
  66. 			{
  67. 				cin>>mat[j][k];
  68. 			}
  69. 			solve_row(j, 1, m);
  70. 		}
  71. 		for (int j = 1; j <= m; j++)
  72. 		{
  73. 			solve_col(j, 1, n);
  74. 		}
  75. 		for (int j = 1; j <= n; j++)
  76. 		{
  77. 			for (int k = 1; k <= m; k++)
  78. 			{
  79. 				for (int l = j-1; l >= 1; l--)
  80. 				{
  81. 					for (int y = k-1; y >= 1; y--)
  82. 					{
  83. 						ll maxim_ans = 0;
  84. 						ll minim = min(minim_ans[l][y+1][j][k], minim_ans[l][y][j][y]);
  85. 						minim_ans[l][y][j][k] = minim;
  86. 						for (int z = j; z > l; z--)
  87. 						{
  88. 							maxim_ans = max(maxim_ans, (ans[l][y][z-1][k]+ans[z][y][j][k]));
  89. 						}
  90. 						for (int z = k; z > y; z--)
  91. 						{
  92. 							maxim_ans = max(maxim_ans, (ans[l][y][j][z-1]+ans[l][z][j][k]));
  93. 						}
  94. 						ans[l][y][j][k] = maxim_ans+minim;
  95. 					}
  96. 				}
  97. 			}	
  98. 		}
  99. 		ll ans1 = ans[1][1][n][m];
  100. 		cout<<"Case #"<<i<<": "<<ans1<<"\n";
  101. 	}
  102. }
Success #stdin #stdout 0s 116800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gmlpjj
language:
C++14 (gcc 8.3)
created:
7 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!