Fișierul intrare/ieșire | parcele.in, parcele.out | Sursă | IZhO 2013 |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Andreescu Mihai • mihai995 |
Timp de execuție pe test | 1.6 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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 |