h3. (clasele 11-12, problema grea)

Problema a fost gandita sa rasplateasca pe "fanii infoarena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/problema/secventa, "Secventa 2":http://infoarena.ro/problema/secv2, "Secventa 3":http://infoarena.ro/problema/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice 2N*2M, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Problema a fost gandita sa rasplateasca pe "fanii infoarena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/problema/secventa, "Secventa 2":http://infoarena.ro/problema/secv2, "Secventa 3":http://infoarena.ro/problema/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice $2N*2M$, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Rezolvarea acum se va baza pe cautarea binara a balansului maxim (idee folosita si la rezolvarea problemei "Secventa 3":http://infoarena.ro/problema/secv3). Fie acesta {$X$}, trebuie sa verificam daca exista o submatrice cu balans cel putin {$X$}, adica: