fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. void maximum(int & a, int b) { a = max(a, b); }
  7.  
  8. vector<ll> candidate[2][2];
  9.  
  10. int n;
  11. vector<int> solution;
  12. vector<vector<vector<int>>> rectangles;
  13. void extend(int first_line, int second_line, int score);
  14. void go_from(int first_line, int second_line, int so_far);
  15.  
  16. int main() 
  17. {
  18. 	scanf("%d", &n);
  19. 	solution.resize(n + 1, 0);
  20. 	rectangles.resize(n + 1);
  21. 	vector< vector<ll> > in(2, vector<ll>(n));
  22. 	for(vector<ll> & row : in)
  23. 		for(int index = 0; index < n; ++index) 
  24. 		{
  25. 			scanf("%lld", &row[index]);
  26. 			if(index) row[index] += row[index-1]; // prefix sums
  27. 		}
  28. 	for(int index0 = 0; index0 <= 1; ++index0)
  29. 		for(int index1 = index0; index1 <= 1; ++index1) 
  30. 		{
  31. 			candidate[index0][index1].resize(n, -1);
  32. 			map<ll, int> next_occurrence;
  33. 			for(int where = n - 1; where >= 0; --where) 
  34. 			{
  35. 				ll new_value = 0;
  36. 				for(int index = index0; index <= index1; ++index)
  37. 					new_value += in[index][where];
  38. 				next_occurrence[new_value] = where;
  39. 				ll need = 0;
  40. 				if(where != 0)
  41. 					for(int index = index0; index <= index1; ++index)
  42. 						need += in[index][where-1];
  43. 				if(next_occurrence.count(need))
  44. 					candidate[index0][index1][where] = next_occurrence[need];
  45. 			}
  46. 		}
  47.  
  48. 	for(int where = 0; where < n; ++where) 
  49. 	{
  50. 		int so_far = solution[where];
  51. 		go_from(where, where, so_far);
  52.  
  53. 		auto minimum = [&] (int & a, int b) 
  54. 		{
  55. 			if(a == -1 || b < a) a = b;
  56. 		};
  57. 		int how_far_up = -1, how_far_down = -1;
  58. 		for(const vector<int> & rect : rectangles[where]) 
  59. 		{
  60. 			if(rect[1] == where && rect[2] == so_far + 1)
  61. 				minimum(how_far_up, rect[0]);
  62. 			if(rect[0] == where && rect[2] == so_far + 1)
  63. 				minimum(how_far_down, rect[1]);
  64. 		}
  65. 		if(how_far_up != -1)
  66. 			go_from(how_far_up, where, so_far + 1);
  67. 		if(how_far_down != -1)
  68. 			go_from(where, how_far_down, so_far + 1);
  69. 	}
  70. 	printf("%d\n", solution[n]);
  71. }
  72.  
  73. void extend(int first_line, int second_line, int score) 
  74. {
  75. 	maximum(solution[max(first_line, second_line)], score);
  76. 	rectangles[min(first_line, second_line)].push_back(vector<int>{first_line, second_line, score});
  77. }
  78.  
  79. void go_from(int first_line, int second_line, int so_far) 
  80. {
  81. 	// extend the first row
  82. 	if(first_line < n) 
  83. 	{
  84. 		extend(first_line + 1, second_line, so_far);
  85. 		int i = candidate[0][0][first_line];
  86. 		if(i != -1)
  87. 			extend(i + 1, second_line, so_far + 1);
  88. 	}
  89. 	// extend the second row
  90. 	if(second_line < n) 
  91. 	{
  92. 		extend(first_line, second_line + 1, so_far);
  93. 		int i = candidate[1][1][second_line];
  94. 		if(i != -1)
  95. 			extend(first_line, i + 1, so_far + 1);
  96. 	}
  97. 	// extend both rows (with a rectangle of height 2)
  98. 	if(first_line == second_line && first_line < n) 
  99. 	{
  100. 		int i = candidate[0][1][first_line];
  101. 		if(i != -1)
  102. 			extend(i + 1, i + 1, so_far + 1);
  103. 	}
  104. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:2:21: fatal error: iosstream: No such file or directory
 #include <iosstream>
                     ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/yKq2Hj
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!