Для того, чтобы решить первую подзадачу достаточно перебрать клетку, в которую встанет Луиджи и воспользоваться методом динамического программирования для подсчета максимального числа очков, которое сможет получить Марио, для каждой выбранной клетки. Сложность такого решения O(n2·m2).
Рассмотрим какой-нибудь оптимальный путь, по которому мог бы идти Марио, если бы Луиджи не занимал бы никакую клетку. Заметим, что максимальное количество очков, которое сможет получить Марио, останется неизменным, если Луиджи займет клетку вне данного пути. Сделаем вывод, что стоит перебирать клетки для Луиджи только среди клеток входящих в оптимальный путь. Такое решение работает за O((n + m)·n·m) и проходит первые две подзадачи.
Наконец заметим, что любой путь проходит ровно через одну клетку каждой побочной диагонали (множество клеток с одинаковой суммой координат). Затем посчитаем максимальные пути от начальной клетки до каждой, а также от каждой до конечной. Тогда для каждой побочной диагонали можно посчитать новый оптимальный ответ, если Луиджи занял клетку в оптимальном пути пересекающую данную диагональ. Для этого среди всех оставшихся клеток на данной диагонали нужно выбрать ту, у которой сумма максимального пути от начальной клетки до нее и от нее до конечной клетки будет максимальной. Чтобы выбирать эту клетку за O(1) можно для каждой диагонали предподсчитать две наибольшие клетки по данной сумме (наибольшая, очевидно, входит в оптимальный путь). Теперь среди вторых максимумов на каждой диагонали нужно выбрать наименьший, он и будет являться ответом на задачу. Итоговая сложность данного решения O(n·m).