fork(5) download
copy 
  1. program problemWombats;
  2. uses math;
  3.  
  4. const	inf =	round(1.0e+15);
  5.  
  6. type	tRec =	record
  7. 					a: array[ 1..12, 1..12 ] of int64;
  8. 					n, cnt: longInt;
  9. 					f: array[ 1..800000, 1..12 ] of longInt;
  10. 					dp: array[ 1..800000 ] of int64;
  11. 				end;
  12.  
  13. var	forSearch: array[ 1..12 ] of longInt;
  14.  
  15. function find( const g: tRec ): longInt;
  16. var	l, r, c, i: longInt;
  17. begin
  18. 	l := 1;
  19. 	r := g.cnt;
  20. 	while ( l < r ) do
  21. 	begin
  22. 		c := ( l + r ) div 2;
  23.  
  24. 		i := 1;
  25. 		while ( i <= g.n ) and ( forSearch[i] = g.f[c][i] ) do
  26. 			inc( i );
  27.  
  28. 		if ( i <= g.n ) and ( g.f[c][i] < forSearch[i] ) then
  29. 			l := c + 1
  30. 		else
  31. 			r := c;
  32. 	end;
  33.  
  34. 	exit( l );
  35. end;
  36.  
  37. procedure generateStates( var g: tRec );
  38. var	i, j: longInt;
  39. begin
  40. 	with g do
  41. 	begin
  42. 		cnt := 1;
  43. 		for i := 1 to n do
  44. 			f[1][i] := 0;
  45.  
  46. 		while ( true ) do
  47. 		begin
  48. 			i := n;
  49. 			while ( i > 1 ) and ( f[cnt][i] = min( f[cnt][i - 1], n - i + 1 ) ) do
  50. 				dec( i );
  51.  
  52. 			if ( i = 1 ) and ( f[cnt][i] = n ) then
  53. 				break;
  54.  
  55. 			inc( cnt );
  56. 			for j := 1 to i - 1 do
  57. 				f[cnt][j] := f[cnt - 1][j];
  58.  
  59. 			f[cnt][i] := f[cnt - 1][i] + 1;
  60.  
  61. 			for j := i + 1 to n do
  62. 				f[cnt][j] := 0;
  63. 		end;
  64.  
  65. 		for i := 1 to cnt do
  66. 			dp[i] := -inf;
  67. 	end;
  68. end;
  69.  
  70. procedure processTransition( var g2, g: tRec );
  71. var	i, j: longInt;
  72. begin
  73. 	with g do
  74. 	begin
  75. 		for i := 1 to cnt do
  76. 		begin
  77. 			for j := 1 to n - 1 do
  78. 				forSearch[j] := min( f[i][j], n - j );
  79.  
  80. 			j := find( g2 );
  81.  
  82. 			g2.dp[j] := max( g2.dp[j], dp[i] );
  83. 		end;
  84. 	end;
  85. end;
  86.  
  87. procedure calculateDP( var g: tRec );
  88. var	i, j, k: longInt;
  89. begin
  90. 	with g do
  91. 	begin
  92. 		for i := cnt downto 1 do
  93. 		begin
  94. 			for j := 1 to n do
  95. 				forSearch[j] := f[i][j];
  96.  
  97. 			if ( n <> 12 ) then
  98. 			begin
  99. 				for j := 1 to n do
  100. 					if ( f[i][j] > 0 ) and ( ( j = n ) or ( f[i][j + 1] < f[i][j] ) ) then
  101. 					begin
  102. 						dec( forSearch[j] );
  103.  
  104. 						k := find( g );
  105.  
  106. 						dp[k] := max( dp[k], dp[i] );
  107.  
  108. 						inc( forSearch[j] );
  109. 					end;
  110. 			end;
  111.  
  112. 			for j := 1 to n do
  113. 				for k := 1 to f[i][j] do
  114. 					inc( dp[i], a[j + k - 1][j] );
  115. 		end;
  116. 	end;
  117. end;
  118.  
  119. var	f: array[ 0..1 ] of tRec;
  120. 	n, i, j, k: longInt;
  121. 	a: array[ 1..12, 1..12, 1..12 ] of longInt;
  122. 	ans: int64;
  123.  
  124. begin
  125. 	readln( n );
  126. 	for i := 1 to n do
  127. 		for j := 1 to i do
  128. 			for k := 1 to i + 1 - j do
  129. 				read( a[i][j][k] );
  130.  
  131. 	f[n mod 2].n := n;
  132. 	for i := 1 to n do
  133. 		for j := 1 to i do
  134. 			f[n mod 2].a[i][j] := a[i][i + 1 - j][j];
  135.  
  136. 	generateStates( f[n mod 2] );
  137. 	for i := 1 to f[n mod 2].cnt do
  138. 		f[n mod 2].dp[i] := 0;
  139.  
  140. 	calculateDP( f[n mod 2] );
  141.  
  142. 	for k := n - 1 downto 1 do
  143. 	begin
  144. 		f[k mod 2].n := k;
  145. 		for i := 1 to k do
  146. 			for j := 1 to i do
  147. 				f[k mod 2].a[i][j] := a[ i + (n - k) ][i + 1 - j][j];
  148.  
  149. 		f[k mod 2].cnt := 0;
  150.  
  151. 		generateStates( f[k mod 2] );
  152. 		processTransition( f[k mod 2], f[ (k + 1) mod 2 ] );
  153. 		calculateDP( f[k mod 2] );
  154. 	end;
  155.  
  156. 	ans := 0;
  157. 	for i := 1 to f[1].cnt do
  158. 		ans := max( ans, f[1].dp[i] );
  159. {		
  160. 	for i := 1 to n do
  161. 	begin
  162. 		writeln( 'Layer #', i, ': ' );
  163.  
  164. 		for j := 1 to i do
  165. 		begin
  166. 			for k := 1 to j do
  167. 				write( f[i].a[j][k], ' ' );
  168. 			writeln();
  169. 		end;
  170.  
  171. 		for j := 1 to f[i].cnt do
  172. 		begin
  173. 			write( j:3, ' ' );
  174. 			for k := 1 to i do
  175. 				write( f[i].f[j][k], ' ' );
  176.  
  177. 			writeln( f[i].dp[j] );
  178. 		end;
  179. 	end;
  180. }	
  181. 	writeln( ans );
  182. end.
  183.  
Runtime error #stdin #stdout 0.13s 96960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0wqCm5
language:
Pascal (fpc 3.0.4)
created:
10 years 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!