fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using lint = long long;
  4. using pi = array<lint, 2>;
  5. #define sz(v) ((int)(v).size())
  6. #define all(v) (v).begin(), (v).end()
  7. const int MAXN = 105;
  8.  
  9. // n^
  10. // d[i, h] -> d[i + 1, h]
  11. // d[j, h ^ sum[i, j]]
  12. int main() {
  13. 	ios_base::sync_with_stdio(0);
  14. 	cin.tie(0);
  15. 	cout.tie(0);
  16. 	int tc;
  17. 	cin >> tc;
  18. 	for (int i = 1; i <= tc; i++) {
  19. 		cout << "Case #" << i << ": ";
  20. 		int n, m;
  21. 		cin >> n >> m;
  22. 		vector<vector<lint>> a(n + 2, vector<lint>(m + 2));
  23. 		vector<vector<lint>> d1(n + 2, vector<lint>(m + 2));
  24. 		vector<vector<lint>> d2(n + 2, vector<lint>(m + 2));
  25. 		vector<vector<lint>> up(n + 2, vector<lint>(m + 2, 1e18));
  26. 		vector<vector<lint>> le(n + 2, vector<lint>(m + 2, 1e18));
  27. 		for (int i = 1; i <= n; i++) {
  28. 			for (int j = 1; j <= m; j++) {
  29. 				cin >> a[i][j];
  30. 			}
  31. 		}
  32. 		for (int i = 1; i <= n; i++) {
  33. 			for (int j = 1; j <= m; j++) {
  34. 				d1[i][j] = max(d1[i][j - 1], d1[i - 1][j]) + a[i][j];
  35. 			}
  36. 		}
  37. 		for (int i = n; i > 0; i--) {
  38. 			for (int j = m; j > 0; j--) {
  39. 				d2[i][j] = max(d2[i][j + 1], d2[i + 1][j]) + a[i][j];
  40. 			}
  41. 		}
  42. 		up[1][m] = le[1][m] = -1e18;
  43. 		for (int i = 1; i <= n; i++) {
  44. 			for (int j = m; j >= 1; j--) {
  45. 				{
  46. 					lint d1max = d1[i - 1][j], summax = -1e18;
  47. 					for (int k = i + 1; k <= n; k++) {
  48. 						d1max = max(d1max, d1[k - 1][j - 1]);
  49. 						if (k > i + 1)
  50. 							summax = max(summax, d1max + d2[k - 1][j + 1]);
  51. 						up[k][j] = min(up[k][j], max({d1max + max(d2[k + 1][j], d2[k][j + 1]), summax, le[i][j]}));
  52. 					}
  53. 				}
  54. 				{
  55. 					lint d2max = d2[i][j + 1], summax = -1e18;
  56. 					for (int l = j - 1; l >= 1; l--) {
  57. 						d2max = max(d2max, d2[i + 1][l + 1]);
  58. 						if (l < j - 1)
  59. 							summax = max(summax, d2max + d1[i - 1][l + 1]);
  60. 						le[i][l] = min(le[i][l], max({d2max + max(d1[i][l - 1], d1[i - 1][l]), summax, up[i][j]}));
  61. 					}
  62. 				}
  63. 			}
  64. 		}
  65. 		cout << min(up[n][1], le[n][1]) << "\n";
  66. 	}
  67. }
Runtime error #stdin #stdout #stderr 0.01s 5380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/hB5DXP
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!