@Anuto4ka

Задано прямоугольную таблицу размером M строк на N столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.
Будем снисходительными к Путнику, считая «хорошими» не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на K.
Количество «хороших» путей гарантированно не превышает 109.
Задание
Напишите программу GOODWAYS, находящую значение максимально возможной суммы и количества «хороших» путей.
Входные данные
Первая строка входного файла GOODWAYS.DAT содержит три целых числа M (2≤M≤200), N (2≤N≤200) и K (0≤K≤200). Каждая из последующих M строк содержит N чисел, записанных в соответствующих клеточках.
Выходные данные
Первая строка выходного файла GOODWAYS.SOL должна содержать максимальную возможную сумму; вторая строка – количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.
Пример входных и выходных данных
GOODWAYS.DAT
2 3 3
1 9 7
2 5 3

GOODWAYS.SOL
20
2

Помогите решить пожалуйста,уж очень нужно

0

@odip

Видимо 10^9.

Вообще это задача олимпиадная.

Добавлено через 4 минуты
Сначала находим оптимальный маршрут методом динамического программирования.
Определяем cумму оптимального маршрута - sum_optim.

Потом делаем перебор всех маршрутов и подсчитываем те маршруты сумма которых >= sum_optim-k.

1