|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 19-1. Симпатичные таблицы.
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 2 секунды |
Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает Ri и для всех j сумма чисел ее j-го столбца не превышает Cj.
Вам задана таблица Z размера MxN, в некоторых клетках которой уже стоят целые неотрицательные числа. Найдите симпатичную таблицу с максимальной суммой элементов такую, что она совпадает с Z на тех клетках, в которых в Z стоят числа.
Формат входных данных
Первая строка входного файла содержит числа M и N (1 <= M, N <= 20).
Следующая строка содержит M целых неотрицательных чисел - R1,
R2, ..., RM. Следующая строка содержит N целых
неотрицательных чисел C1, C2, ..., CN. Все
ограничения не превышают 106. Следующие M строк содержит по N целых
чисел, которые задают Z. Если на некотором месте в таблице отсутствует число,
то на этом месте во входном файле стоит число -1.
Формат выходных данных
Выведите в выходной файл найденную таблицу - M строк по N чисел. Если решения
не существует, выведите единственное число -1.
Пример
| input.txt | output.txt |
2 2 2 2 1 2 1 -1 -1 -1 |
1 1 0 1 |