Ещё больше веселья
Ещё больше веселья
Так прекрасно спать под открытым небом, просыпаться под пение птиц и видеть первые лучи солнца, встающего из-за горизонта...
Стоп, Вы же не помните, как уснули посреди леса. Единственное, что Вы помните, это что Вы покрывали что-то тремя прямоугольниками. 0_о
Будучи неуверенным в том, что же это было, Вы придумали себе следующую задачу: Для данной матрицы, состоящей из целых чисел, найти k неперекрывающихся подматриц (другими словами, прямоугольных фрагментов) таких, что сумма чисел в них была бы наибольшей.
Giriş verilənləri
В первой строке ввода находятся три целых числа n, m и k (1 ≤ k ≤ 3, k ≤ n, m ≤ 300), задающих количество строк, количество столбцов, и число подматриц соответственно. Следующие n чисел описывают матрицу построчно. Каждая из них содержит последовательность m целых чисел a_ij (-20000 ≤ a_ij ≤ 20000). Также известно, что в 40% тестов 1 ≤ k ≤ 2.
Çıxış verilənləri
Выведите одно целое число: наибольшую возможную сумму чисел в k подматрицах данной матрицы. Подматрицы могут касаться, но они не могут иметь общих элементов.
Nümunə
4 5 2 6 -10 0 3 -6 -8 8 1 -5 3 -7 -3 2 4 -4 2 0 -1 3 -3
17