Covor
Fie T[i][j] cea mai lungă secvenţă continuă cu 0 de pe linia i, având ca ultim element (i, j). Numărul de matrice pline cu 0 ce au în colţul dreapta-jos elementul (i, j) este T[i][j](cele de înalţime 1) + min(T[i][j], T[i-1][j])(cele de înălţime 2) + ... + min(T[i][j], T[i-1][j], ..., T[1][j])(cele de înalţime j). Implementarea directă a acestei relaţii are complexitatea O(N3) şi aduce 50 de puncte.
Pentru a obţine complexitatea O(N2), vom parcurge elementele pe coloane şi vom menţine o stivă ordonată crescător cu elementele din matricea T. Suplimentar, pentru fiecare element, vom reţine şi pentru câţi dintre termenii sumei prezentate anterior va fi elementul minim. Astfel, când dorim să introducem elementul T[i][j] în stivă, vom elimina elementele mai mari decât el şi vom adăuga la numărul asociat acestui element numerele asociate elementelor eliminate. La fiecare pas se adaugă la rezultat suma produsului dintre fiecare element din stivă şi numărul asociat lui.
