Темы --> Информатика --> Алгоритмы --> Динамическое программирование
    Рекуррентные последовательности(10 задач)
    Динамическое программирование: один параметр(49 задач)
    Динамическое программирование: два параметра(183 задач)
    Динамическое программирование в играх(9 задач)
    Динамическое программирование на графах(25 задач)
    Динамическое программирование по профилю(20 задач)
    Динамика по подмножествам(13 задач)
---> 1 задач <---
Источники --> Личные олимпиады --> Украинские олимпиады
    1999(3 задач)
    2000(5 задач)
    2001(4 задач)
    2002(7 задач)
    2003(3 задач)
    2004(6 задач)
    2005(5 задач)
    2006(6 задач)
    2007(6 задач)
    2008(5 задач)
    2009(6 задач)
    2010(0 задач)
    2011(0 задач)
    2012(0 задач)
    2013(0 задач)
    2016(5 задач)
Страница: 1 Отображать по:
#1635
Альтернативные пути
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Задано прямоугольную таблицу размером \(M\) строк на \(N\) столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.

Будем снисходительными к Путнику, считая «хорошими» не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на \(K\).

Количество «хороших» путей гарантированно не превышает \(10^9\).

Напишите программу, находящую значение максимально возможной суммы и количества «хороших» путей.

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

Первая строка входного файла содержит три целых числа \(M\) (2≤\(M\)≤200), N (2≤\(N\)≤200) и \(K\) (0≤\(K\)≤200). Каждая из последующих \(M\) строк содержит \(N\) чисел, записанных в соответствующих клеточках.

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

Первая строка выходного файла должна содержать максимальную возможную сумму; вторая строка – количество маршрутов, сумма чисел которых отличается от максимальной не более чем на \(K\).

Примеры
Входные данные
2 3 3
1 9 7
2 5 3
Выходные данные
20
2
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест