Дана таблица n × m (n строк и m столбцов), в каждой ячейке которой стоит «0» или «1».
Требуется посчитать количество прямоугольников со сторонами, параллельными сторонам таблицы и проходящими по границам ячеек, таких, что количество единиц в прямоугольнике равно k.
В первой строке, разделенные пробелами, записаны три целых числа n, m и k (1 ≤ n, m ≤ 2500, 0 ≤ k ≤ 6) — размеры таблицы и требуемое количество единиц.
В следующих n строках записано по m символов «0» или «1». i-й символ j-й строке соответствует символу, находящемуся в j-й строке и i-м столбце таблицы.
Выведите единственное число — количество прямоугольников, количество единиц в которых равно k.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
3 3 2 101 000 101
8
5 5 1 00000 00000 00100 00000 00000
81
5 5 6 01010 10101 01010 10101 01010
12
3 3 0 001 010 000
15
4 4 0 0000 0101 0000 0000
52
12000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач