CSES - Datatähti 2020 loppu - Aliruudukot
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Sinulle annetaan $n \times m$ -ruudukko, jonka jokaisella ruudulla on väri.

Tehtäväsi on etsiä pinta-alaltaan suurin aliruudukko, jolla on seuraava ominaisuus: kaikilla poluilla aliruudukon vasemmasta yläkulmasta oikeaan alakulmaan, joissa kuljetaan vain oikealle tai alas, on samat värit täsmälleen samassa järjestyksessä.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$.

Seuraavat $n$ riviä kuvaavat ruudukon. Jokaisella rivillä on $m$ merkkiä väliltä A–Z, jotka kuvaavat värit.

Tuloste

Tulosta yksi kokonaisluku: suurimman kelvollisen aliruudukon pinta-ala.

Esimerkki

Syöte:
3 5
AABAC
ABACA
ABCAA


Tuloste:
10

Osatehtävä 1 (29 pistettä)
  • $1\le n, m\le 10$
Osatehtävä 2 (34 pistettä)
  • $1\le n, m\le 100$
Osatehtävä 3 (37 pistettä)
  • $1\le n, m\le 1000$