Этот день настал! Сегодня, после стольких лет тренировок, Эш наконец-то попал на всемирный турнир тренеров покемонов

Этот день настал! Сегодня, после стольких лет тренировок, Эш наконец-то попал на всемирный
турнир тренеров покемонов, где у него будет шанс побороться за звание лучшего тренера покемонов
в мире. Успешно справившись с несколькими этапами соревнования, Эш попал в финал, в котором
тренированных покемонов проверяют на умение быстро строить оптимальные маршруты.
Один раунд соревнования выглядит следующим образом: покемона помещают в левую верхнюю
клетку прямоугольного поля. В каждой клетке поля записано целое число — количество очков,
которое покемон получает, когда наступает на эту клетку (в клетке может быть записано отрицательное число, это означает, что в случае, если покемон наступает на эту клетку, его количество
очков уменьшается). Задача покемона — добежать до правой нижней клетки поля, получив наибольшее количество очков, при этом, правилами турнира разрешено перемещаться за один шаг
только на одну клетку вправо или на одну клетку вниз.
Перед началом соревнования Эш решил лишний раз удостовериться, что его лучший покемон
— Пикачу умеет строить оптимальные маршруты, для этого он играет с ним в следующую игру:
Эш показывает Пикачу поле и задает ему q вопросов вида «какой наибольший счет можно было бы
получить на этом поле, если бы в клетке с координатами (i, j) было записано число x вместо того,
что там записано сейчас?».
Эш попросил вас написать программу, которая найдет правильные ответы на все вопросы, чтобы
он мог убедиться, что Пикачу готов к финальному соревнованию.
Формат входных данных
В первой строке через пробел записаны 3 числа: n, m и q (1 6 n, m 6 1 000, 1 6 q 6 5 · 105
) —
высота поля, ширина поля и количество вопросов соответственно. Далее в n строках записано по
m целых чисел — значения, которые записаны в клетках поля, не превосходят 106 по абсолютному
значению. Далее в q строках записано по 3 целых числа i, j и x (1 6 i 6 n, 1 6 j 6 m, −106 6 x 6 106
)
— номер строки, столбца клетки и новое значение клетки поля соответственно. Строки нумеруются
сверху вниз, начиная с 1, столбцы нумеруются слева направо, начиная с 1.
Формат выходных данных
Для каждого вопроса выведите одно число — наибольший счет, который можно получить на
данном поле с измененным значением одной клетки.

1

4-я задача с муниципального этапа в МО. какие проблемы?

0