eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ещё больше веселья

Ещё больше веселья

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB

Так прекрасно спать под открытым небом, просыпаться под пение птиц и видеть первые лучи солнца, встающего из-за горизонта...

Стоп, Вы же не помните, как уснули посреди леса. Единственное, что Вы помните, это что Вы покрывали что-то тремя прямоугольниками. 0_о

Будучи неуверенным в том, что же это было, Вы придумали себе следующую задачу: Для данной матрицы, состоящей из целых чисел, найти k неперекрывающихся подматриц (другими словами, прямоугольных фрагментов) таких, что сумма чисел в них была бы наибольшей.

Giriş verilənləri

В первой строке ввода находятся три целых числа n, m и k (1k3, kn, m300), задающих количество строк, количество столбцов, и число подматриц соответственно. Следующие n чисел описывают матрицу построчно. Каждая из них содержит последовательность m целых чисел a_ij (-20000a_ij20000). Также известно, что в 40% тестов 1k2.

Çıxış verilənləri

Выведите одно целое число: наибольшую возможную сумму чисел в k подматрицах данной матрицы. Подматрицы могут касаться, но они не могут иметь общих элементов.

Nümunə

Giriş verilənləri #1
4 5 2
6 -10 0 3 -6
-8 8 1 -5 3
-7 -3 2 4 -4
2 0 -1 3 -3
Çıxış verilənləri #1
17