Каждое утро в 8:30 школьники в ЛКШ
собираются на зарядку перед главным корпусом. Мальчики и девочки становятся на
асфальт, образуя прямоугольную сетку.
На крыльце
здания стоит фотограф. Он хочет сделать групповую фотографию некоторых
мальчиков и девочек. Для этого ему нужно выбрать прямоугольную область на
асфальте так, чтобы внутри неё было поровну мальчиков и девочек. К сожалению
для ЛКШат, таких областей может быть много. Фотограф хочет сделать фотографии
всех этих областей, чтобы выбрать лучшую. На каждую фотографию у него уходит
одна секунда. Таким образом, школьники будут продолжать делать зарядку столько
секунд, сколько существует подходящих подпрямоугольников!
Представим, что
на асфальте перед зданием проведена система координат. Тогда школьники стоят в
целочисленных точках, образуя прямоугольник размером h ? w с осями, параллельными сторонам координат. Фотографу
необходимо выбрать подпрямоугольник с такими же ориентациями сторон.
Напишите
программу, которая вычисляет, сколько секунд школьники будут делать зарядку.
Вход. Первая строка содержит два натуральных числа h и w
(1 ≤ h, w ≤ 300) – размеры прямоугольника,
образованного школьниками. В каждой из последующих h строк находятся по w
чисел. Число 0 означает, что на позиции стоит мальчик, а число 1 – что
стоит девочка.
Выход. Выведите количество секунд, в течение которых будет длиться
зарядка.
|
Пример
входа 1 |
Пример
выхода 1 |
|
3 4 0 1 0 0 1 0 1 1 0 0 0 1 |
20 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
3 1 0 0 0 |
0 |
динамическое
программирование