http://acm.pku.edu.cn/JudgeOnline/problem?id=1191

Код:
program PKU1191;
{$i-,s-,q-,r-}
const maxn = 15;
maxm = 8;
none = 1000000;
type integer = longint;
var s: array[0 .. maxm, 0 .. maxm] of integer;
f: array[1 .. maxm, 1 .. maxm, 1 .. maxm, 1 .. maxm, 1..maxn] of double;
n: integer;
function min(i, j: double): double;
begin
if i < j then min := i else min := j;
end;
procedure prepare;
var i, j, k: integer;
begin
fillchar(s, sizeof(s), 0);
read(n);
for i := 1 to 8 do
for j := 1 to 8 do begin
read(k);
s[i, j] := s[i - 1, j] + s[i, j - 1] - s[i - 1, j - 1] + k;
end;
end;
function calc(x0, x1, y0, y1: integer): integer;
begin
calc := s[x1, y1] - s[x1, y0 - 1] - s[x0 - 1, y1] + s[x0 - 1, y0 - 1];
end;
procedure main;
var i, j, u, v, a, b, k: integer;
mid: double;
begin
mid := s[8, 8] / n;
for i := 0 to 7 do
for u := 1 to 8 - i do
for j := 0 to 7 do
for v := 1 to 8 - j do begin
f[u, i + u, v, j + v, 1] := sqr(mid - calc(u, i + u, v, j + v));
for k := 2 to n do begin
f[u, i + u, v, j + v, k] := none;
if k <= i + j then
for a := u to i + u - 1 do begin
f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
f[u, a, v, j + v, 1] + f[a + 1, i + u, v, j + v, k - 1]);
f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
f[u, a, v, j + v, k - 1] + f[a + 1, i + u, v, j + v, 1]);
end;
for a := v to j + v - 1 do begin
f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
f[u, u + i, v, a, 1] + f[u, u + i, a + 1, v + j, k - 1]);
f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
f[u, u + i, v, a, k - 1] + f[u, u + i, a + 1, v + j, 1]);
end;
end;
end;
writeln(sqrt(f[1, 8, 1, 8, n] / n):1:3);
end;
begin
prepare;
main;
end.