Прямоугольная вертолётная посадочная площадка состоит из квадратов одинакового размера, расположенных в N строк и M столбцов. В ожидании прибытия V вертолётов необходимо разместить на площадке K (K<=N*M-V) контейнеров (те квадраты, на которые сядут вертолёты, занимать нельзя). Каждый контейнер может иметь различный вес Zi, но при этом имеет одинаковый размер (занимает один квадрат). Для вычисления длины пути будем использовать манхэттенское расстояние (разница по столбцам плюс разница по строкам). Стоимость погрузки контейнера в вертолёт равна его весу, умноженному на длину пути до ближайшего вертолёта. Необходимо расположить контейнеры так, чтобы суммарная стоимость их погрузки S была минимальна. Вывести S и любой из вариантов оптимальной расстановки контейнеров (пустые площадки вывести как 0). При выводе только S начисляется половина баллов. Все числа - натуральные, N и M не превышают 100, количество квадратов под вертолёты не превышает половины общего количества квадратов посадочной площадки, вес контейнера не превышает 99, N*M>1.
X1 Y1
…
XV YV
Z1 … ZK
A11 A12 … A1M
A21 A22 … A2M
… … … …
AN1 AN2 … ANM
input.txt | output.txt |
---|---|
3 3 1 6 1 1 5 2 6 4 1 3 |
32 0 6 4 5 3 1 2 0 0 |
3 3 2 6 1 1 3 3 5 2 6 4 1 3 |
24 0 6 2 5 1 4 0 3 0 |
1 5 1 4 1 3 8 8 1 3 |
24 1 8 0 8 3 |
Во втором примере: 6+5+4+3+(1+2)*2 = 24
В третьем примере: 8+8+(1+3)*2 = 24