Županijsko natjecanje iz informatike 2019. / Druga podskupina (3. i 4. razred) - 2. zadatak

Mirko želi kupiti dio velikog zemljišta dimenzija N × N metara koje predstavljamo matricom od N redaka i N stupaca podijeljenom na N × N polja.

Mirko želi da njegov odabrani dio unutar zemljišta bude kvadratnog oblika, tj. da zauzima K × K polja za neki K između 1 i N (uključivo).

Odabrani dio može se nalaziti bilo gdje unutar velikog zemljišta; jedini je uvjet da taj dio zemljišta bude što plodniji.

Za svako polje zemljišta (1 × 1) poznata je njegova plodnost izražena kao cijeli broj – što je broj veći, to je polje plodnije, a plodnost može biti i negativna.

Mirko će procijeniti ukupnu plodnost dijela zemljišta koji planira kupiti.

Na prvi pogled mogao bi samo zbrojiti plodnosti pripadnih polja, ali njegova je formula malo zanimljivija jer mu je za polja koja su bliža središtu kupljenog dijela važnije da budu plodna.

Mirko će dobiti svoju procjenu na sljedeći način:

*plodnosti polja na rubu odabranog kvadrata pomnožit će s 1,

• za dio kvadrata bez tog ruba (kvadrat dimenzije smanjene za dva) plodnosti polja na njegovom rubu pomnožit će s 2,

• rub novog ostatka pomnožit će s 3, i tako dalje, množeći sve većim brojevima plodnosti polja koja su bliža središtu, kao na sljedećim skicama za K = 4 i K = 5:

  

Zbroj navedenih umnožaka daje Mirkovu procjenu. Pomozite Mirku i pronađite kvadrat unutar zadanog zemljišta za koji će njegova procjena plodnosti biti najveća.

ULAZNI PODACI

U prvom retku nalazi se prirodan broj N (2 ≤ N ≤ 400), dimenzija zemljišta.

U sljedećih N redaka nalazi se po N cijelih brojeva iz intervala [-1000, 1000], plodnosti odgovarajućih polja zemljišta.

IZLAZNI PODACI

U jedini redak ispišite najveću plodnost nekog kvadratnog dijela zemljišta.

PRIMJERI TEST PODATAKA

Ulaz

2
1 -7
4 5

Izlaz

5

Objašnjenje

Pojašnjenje prvog primjera: Odabrat ćemo jedinični kvadrat plodnosti 5. Kad bismo odabrali cijeli 2 × 2 kvadrat, dobivena plodnost bila bi 1 - 7 + 4 + 5 = 3.

Ulaz

3
1 2 -3
4 5 6
7 -8 -9

Izlaz

12

Objašnjenje

Pojašnjenje drugog primjera: Odabrat ćemo 2 x 2 kvadrat u gornjem lijevom dijelu.

Ulaz

3
-3 4 5
7 9 -2
1 0 -6

Izlaz

24

Objašnjenje

Pojašnjenje trećeg primjera: Odabrat ćemo cijeli 3 × 3 kvadrat.