241 BMatrix

[•vendetta]

Salut ! Imi spune cineva cum ajung la complexitatea o(n^2); in momentul de fata am n^3 : iau cate o linie si presupun ca un dreptunghi se afla deasupra liniei si celalalt dedesubt(la fel si pt fiecare coloana); un dreptunghi de arie maxima il aflu in n^2;

[•cojocarugabi]

test 2 este
10 10
1101111110
1001111110
1001111110
1111110100
1111111101
1111111111
1000111011
0000111111
1100011110
0110111111
iar raspunsul este 10,de ce?
Singurul raspuns pe care il vad este 9 facut de dreptunghiurile (7,2)-(8,4) si (9,3)-(9,5)

[•klamathix]

Alegi gresit al doilea dreptunghi. Uita-te pe primele linii. Ai unul de 2 x 2 in stanga si unul de 4 x 1 in dreapta.