Чудик в Цветландии Условие

Однажды Чудик попал в загадочную страну Цветландию. Эта страна имеет форму квадрата, разделённого на N × N маленьких квадратиков — регионов.

В каждом регионе растут цветы определённого сорта. У цветов каждого сорта есть определённый период цветения T. Цветы растут T дней, после чего увядают и начинают расти заново.

Цветы каждого региона в каждый из дней имеют определённую силу запаха. В первый день роста цветы не пахнут (сила запаха равна нулю), затем сила запаха увеличивается на единицу каждый день, вплоть до дня увядания. Таким образом, цветы с периодом цветения T в k-й день имеют силу запаха (k − 1) mod T.

Чудик очень любит нюхать цветы, поэтому он хочет выбрать свой маршрут путешествия по Цветландии так, чтобы как можно сильнее ощутить запах цветов.

Чудик выбирает, с какого региона он начнёт путешествие, и отправляется в путь. Путешествие Чудика длится K дней. За один день Чудик должен переместиться в соседний (сверху, справа, снизу или слева) регион.

В k-й день путешествия Чудика в регионе с координатами (x, y) цветы имеют силу запаха (k − 1) mod T(x, y), где T(x, y) — период цветения цветов этого региона.

Чудик хочет выбрать маршрут так, чтобы сумма сил запаха в регионах, через которые он пройдёт, была максимальной.

Комментарий к примеру

Силы запаха в регионах по дням:

1	2	3	4
0 0 0 0	1 1 1 1	0 0 2 0	1 1 0 1

Формат входного файла

Входной файл содержит целые числа N K. Далее следуют N² целых чисел T(x, y).

Формат выходного файла

Выходной файл должен содержать целое число — максимальную сумму сил запаха.

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 100

2 ≤ T(x, y) ≤ 100

Примеры тестов

№	Входной файл	Выходной файл
1	2 4 2 2 3 2	4

Разбор

Применим метод динамического программирования, который заключается в следующем. Исходная задача разбивается на подзадачи. Затем выводится рекуррентное соотношение, связывающее решение большей подзадачи с решениями меньших подзадач. Рекуррентное соотношение позволяет вычислить решение большей подзадачи, если решения меньших подзадач уже вычислены. Подзадачи решаются от меньших к бóльшим, и в конечном итоге мы приходим к решению исходной задачи.

Подзадача: найти максимальную сумму сил запаха, если прошло k дней и на k-й день Чудик оказался в регионе с координатами (x, y).

Пусть f(x, y, k) — решение такой подзадачи.

Пусть a(x, y, k) — сила запаха в регионе с координатами (x, y) в k-й день: a(x, y, k) = (k − 1) mod T(x, y).

f(x, y, 1) = a(x, y, 1) = 0.

Рекуррентное соотношение: f(x, y, k) = a(x, y, k) + max{f(x − 1, y, k − 1), f(x + 1, y, k − 1), f(x, y − 1, k − 1), f(x, y + 1, k − 1)}.

Решение исходной задачи: max f(x, y, K), где максимум берётся по всем x, y от 1 до N.

program chudik;

const

MAX_N = 100;

MAX_K = 100;

var

a: array[0..MAX_K-1, 1..MAX_N, 1..MAX_N] of integer;

f: array[0..MAX_K-1, 1..MAX_N, 1..MAX_N] of integer;

T: array[1..MAX_N, 1..MAX_N] of integer;

N, K: integer;

m: integer;

i, j, l: integer;

begin

assign(input, 'input.txt');

reset(input);

assign(output, 'output.txt');

rewrite(output);

read(N, K);

for i := 1 to N do

begin

for j := 1 to N do

read(T[i,j]);

end;

for l := 0 to K-1 do

begin

for i := 1 to N do

begin

for j := 1 to N do

a[l,i,j] := l mod T[i,j];

end;

end;

for i := 1 to N do

begin

for j := 1 to N do

f[0,i,j] := a[0,i,j];

end;

for l := 1 to K-1 do

begin

for i := 1 to N do

begin

for j := 1 to N do

begin

m := 0;

if ((i > 1) and (f[l-1,i-1,j] > m)) then

m := f[l-1,i-1,j];

if ((i < N) and (f[l-1,i+1,j] > m)) then

m := f[l-1,i+1,j];

if ((j > 1) and (f[l-1,i,j-1] > m)) then

m := f[l-1,i,j-1];

if ((j < N) and (f[l-1,i,j+1] > m)) then

m := f[l-1,i,j+1];

f[l,i,j] := a[l,i,j] + m;

end;

end;

end;

m := 0;

for i := 1 to N do

begin

for j := 1 to N do

begin

if (f[K-1,i,j] > m) then

m := f[K-1,i,j];

end;

end;

write(m);

close(input);

close(output);

end.