Zadanie

Kvalitný Slovenský Provider je nový mobilný operátor, ktorý práve vyhral grant na pokrytie Chicaga. Žiaľ, dostali iba polovicu finančných prostriedkov o ktoré žiadali. Preto ich nový vysielač síce má neobmedzený dosah, ale funguje iba v štyroch smeroch – Sever, Východ, Juh a Západ.

Podľa podmienok grantu má Kvalitný Slovenský Provider vybudovať vysielače na strechách práve dvoch mrakodrapov. Vysielače chcú umiestniť tak, aby maximalizovali počet potenciálnych zákazníkov, teda tak, aby pokryli čo najväčšie množstvo obyvateľov Chicaga. Vašou úlohou je zistiť najväčší možný počet ľudí, ktorým vedia poskytnúť mobilné pripojenie.

Úloha

Chicago má tvar štvorcovej mriežky so stranou \(n\) políčok. Na každom políčku stojí mrakodrap, v ktorom býva daný počet ľudí. Každý vysielač pokryje všetkých obyvateľov tých mrakodrapov, ktoré sú od neho na Sever, Východ, Juh, alebo Západ. Budovu, na ktorej je postavený, vysielač nevie pokryť. Navyše, ani druhý vysielač ju nemôže pokryť, lebo ich signály sa tu vyrušia.

Vašou úlohou je pre dané rozloženie obyvateľov Chicaga nájsť najväčší možný počet potenciálnych zákazníkov pokrytých aspoň jedným z dvoch vysielačov.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(2\leq n\leq 300\)) udávajúce dĺžku strany Chicaga. Na každom z nasledujúcich \(n\) riadkov je \(n\) čísiel udávajúcich počty obyvateľov na jednotlivých políčkach štvorca. Počet obyvateľov na jednom políčku je nezáporný a neprevyšuje \(10^3\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo – maximálny možný počet potenciálnych zákazníkov.

Príklady

Input:

3
1 2 3
3 2 1
2 2 2

Output:

14

Vysielače môžu byť postavené napríklad na mrakodrapoch s jedným obyvateľom.

Input:

2
2 2
2 2

Output:

4

Každé rozmiestnenie vysielačov je optimálne. Dva mrakodrapy bez vysielača majú pokrytie, a dva mrakodrapy s vysielačom pokrytie nemajú.

Hrubá sila

Riešenie hrubou silou je jednoduché: Vyskúšame všetky možné umiestnenia dvojíc vysielačov, a pre každé spočítame počet pokrytých obyvateľov. Keďže Chicago má \(n^2\) mrakodrapov, možných rozložení dvojice vysielačov je \(O(n^4)\). Ak potom pre každé rozloženie zrátame v konštantnom čase počet pokrytých obyvateľov pomocou predpočítaných súčtov riadkov a stĺpcov, môžeme získať 4 body za riešenie s časovou zložitosťou \(O(n^4)\).

Vzorové riešenie

Na plný počet bodov musíme riešenie hrubou silou o jeden rád zrýchliť na \(O(n^3)\), napríklad takto:

Najprv predpokladáme, že vysielače sú v optimálnom riešení v rôznych riadkoch a stĺpcoch. Vyskúšame každú možnú dvojicu stĺpcov: V oboch stĺpcoch si spočítame pokrytie jedného vysielača na každej pozícií v tomto stĺpci (ignorujúc mrakodrap v druhom stĺpci, keďže ten bude určite pokrytý druhým vysielačom). Použijeme pritom predpočítané súčty riadkov a stĺpcov, podobne ako v riešení vyššie, aby sme každé pokrytie spočítali v \(O(1)\). Ak tieto pokrytia zoradíme, môžeme jednoducho zobrať najlepšie pozície z ľavého a z pravého stĺpca (ak sú v tom istom riadku, skontrolujeme najlepšie dve pozície). Ich súčet nám potom dá najlepšie riešenie s vysielačmi v týchto dvoch stĺpcoch. Takto dosiehneme časovú zložitosť \(O(n^3)\), keďže pre každú z \(O(n^2)\) dvojíc stĺpcov raz prejdeme každý zo stĺpcov s \(n\) mrakodrapmi. Musíme si dať ale pozor, aby sme si namiesto zoraďovania iba vybrali dve najlepšie riešenia, keďže triedenie je príliš pomalé (triedenie \(O(n\, log\, n)\), celý cyklus teda \(O(n^3 \, log \, n)\)).

Ešte musíme vyskúšať možnosť, že v optimálnom riešení sú oba vysielače v tom istom riadku alebo stĺpci: Stačí nám pre každý riadok vyskúšať všetky dvojice stĺpcov, v ktorých sa nachádzajú vysielače, a vybrať najlepšie pokrytie (a podobne pre stĺpce). Časová zložitosť \(O(n^3)\) nám tu stačí, keďže takú má prvá časť tohoto riešenia.

Mimochodom, takáto možnosť naozaj môže nastať. Napríklad pre vstup nižšie sú v optimálnom riešení vysielače na mrakodrapoch s \(0\) obyvateľmi:

Input:

5
1 9 1 9 1
1 9 1 9 1
9 0 9 0 9
1 9 1 9 1
1 9 1 9 1

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.