Привет, Codeforces!
Недавно я столкнулся с интересной задачей на дп (может возможны другие подходы), но пока не могу ее решить.
Дана квадратная таблица размером n на n (n<=1000). Каждая ячейка таблицы либо черная, либо белая. Надо посчитать количество способов выбрать 2 непересекающихся черных прямоугольника. Под черным прямоугольником понимается любая подтаблица (в форме прямоугольника или квадрата) данной матрицы содержащая более 1 клетки и заполненная только черными клетками.
Буду очень благодарен за любую подсказку.
Тест 1
Тест 2
Тест 3
P.S Во всех тестах C — черная клетка, B — белая.
