e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Расположение предприятий

Расположение предприятий

HDWBP Inc. имеет n клиентов, ей следует обслужить их открыв k предприятий. Каждый открытое предприятие может обслужить любое количество клиентов, каждый клиент должен быть обслужен открытым предприятием. Имеется m возможных месторасположений для этих k предприятий. Стоимость обслуживания клиента j в месте i составляет неотрицательное целое cij. Стоимости удовлетворяют свойству локальности: для любых двух клиентов j и j0 и двух предприятий i и i0 имеет место cijci0j + ci0j0 + cij0.

По заданным стоимостям CEO из HDWBP Inc. хочет знать, как открыть k предприятий и назначить им клиентов за как можно меньшую цену. Вы должны определить, можно ли это сделать совсем без денег (то есть со стоимостью ноль).

Входные данные

Первая строка содержит три целых числа m, n, k, где 1m100, 1n100 и 1km. Каждая из следующих m строк содержит n неотрицательных целых чисел, где j-ое целое в i-ой строке равно cij10 000.

Выходные данные

Вывести yes, если можно выполнить задачу со стоимостью ноль; иначе вывести no.

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
3 2 2
0 2
1 1
2 0
Вихідні дані #1
yes
Вхідні дані #2
3 3 2
0 2 2
1 1 1
2 2 0
Вихідні дані #2
no
Джерело 2014 ACM North America - Rocky Mountain, Problem D