Fișierul intrare/ieșire parcele.in, parcele.out Sursă IZhO 2013
Autor autor necunoscut Adăugată de avatar mihai995 Andreescu Mihai mihai995
Timp de execuție pe test 1.6 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Parcele

Bilbo, după ce s-a întors din aventura sa, a decis să-și contruiască o casă nouă, pe o zonă de pământ dreptunghiulară de dimensiune N x M. Fiecare parcelă din această zonă are asociat un grad de frumusețe f. El are de gând să cumpere o zonă de arie minim A și și cu frumusețe maximă. Frumusețea unei zone este frumusețea celei mai “urâte” parcele din zona respectivă.
Pentru că Bilbo nu știe să programeze, vă roagă pe voi să-i determinați frumusețea pe care o va avea zona și aria totală a acesteia (minim A). Dacă există mai multe zone ce respectă condițiile date, Bilbo va alege zona cu aria cea mai mare.

Date de intrare

Pe prima linie din fișierul parcele.in se vor găsi 3 numere, N, M și A, reprezentând dimensiunile zonei, respectiv aria minimă cerută de Bilbo. Pe următoarele N linii, se vor afla câte M numere. Al j-lea număr de pe linia i + 1 va reprezenta frumusețea parcelei (i, j).

Date de ieșire

Fișierul parcele.out va conține 2 numere, F și B, reprezentând gradul maxim de frumusețe al zonei pe care o va achiziționa Bilbo, respectiv aria maximă posibilă a unei zone cu gradul de frumusețe F.

Restricții

  • 1 ≤ N, M ≤ 1 000
  • 1 ≤ A ≤ N x M
  • 1 ≤ f(i, j) ≤ 1 000 000 000
  • Pentru 30% dintre teste, se garanteaza ca f(i, j) ≤ B, oricare 1 ≤ i ≤ N si 1 ≤ j ≤ M
  • Pentru 80% dintre teste, se garanteaza ca 1 ≤ N, M ≤ 500

Exemplu

parcele.in parcele.out
3 3 3
1 1 1
1 2 2
1 2 2
2 4
1 10 5
4 3 2 5 10 7 6 5 1 100
5 5
3 5 2
5 7 5 5 5
8 5 5 7 5
8 5 8 8 8
8 3

Trebuie să te autentifici pentru a trimite soluții. Click aici