SPOJ zawody w szacowaniu przekroczono limit czasu

pytanie zadane 25 lipca 2018 w SPOJ przez paweljumper Obywatel (1,260 p.)
edycja 25 lipca 2018 przez paweljumper

Witam, męczę się już 2 dzień z zadaniem na spoju. Znalazłem stronę na której jest rozpisane rozwiązanie na które sam wpadłem wcześniej, które wg autora postu nie jest na tyle wydajne aby móc przejść przez spoja, podaje drugi sposób I o ile rozumiem, że zamiast tablicy wartości logicznych mam zrobić tablicę int, to druga część rozwiązania jest dla mnie kompletnie niezrozumiała i nie mam pojęcia jak to zaimplementować w programie: link

Przy zliczaniu, kiedy dojdziemy do jakiejś zajętej komórki, po prostu dodamy do wyniku 1 licząc jedynie szczyt piramidy, a następnie dodamy 2 piramidy, o 1 rozmiar mniejsze. Tak więc dla a2,1 wpiszemy w komórki a3,1 i a3,2 wartość 2-1=1, a w komórki a3,2 i a3,3 liczbę 3-1=2. Czyli dzielimy piramidę na: szczyt (złożony z 1 kwadratu), lewą podpiramidę o rozmiarze o 1 mniejszym i prawą podpiramidę o rozmiarze o 1 mniejszym. Jak widzimy, 2 razy zaktualizowaliśmy komórkę a3,2. Musimy pamiętać, że możemy aktualizować komórkę TYLKO na wartość większą. Dotyczy to również wczytywania. Czyli jeśli mamy w jakiejś komórce wartość 5, to możemy ją zmienić na 7, ale odwrotnie już nie (bo interesuje nas maksymalny obszar pokryty przez piramidy).

Czy ktoś byłby w stanie pomóc mi z tym właśnie zliczaniem? Bardzo dziękuję za pomoc.
LINK DO ZADANIA NA SPOJ
Mój kod z rozwiązaniem naiwnym: https://ideone.com/u3Gi1J
Kod z zapisywaniem rozmiarów: https://ideone.com/aIR0zL

komentarz 20 października 2018 przez X3h Dyskutant (9,540 p.)

Jeśli masz rozwiązanie i nie rozumiesz o co chodzi to znak żeby zająć się innym problemem. Kiedyś do tego wrócisz z innym podejściem.

2 odpowiedzi

odpowiedź 20 października 2018 przez Patryk Hołub Nowicjusz (160 p.)

W pętli w której wczytujesz współrzędne oraz wielkość piramidy przypisujesz do danych współrzędnych jej wielkość tylko wtedy, gdy jest większa od wartości tej komórki. Funkcja max() jest wygodna tutaj.

Po wyjściu z tej pętli rozpoczynasz zliczanie wiersz po wierszu. Gdy natkniesz się na wartość większą od 0, dajesz ++result i tworzysz dwie podpiramidy w sposób opisany w tym algorytmie. Czego autor wpisu nie uściślił, a dojście do tego zajęło mi godzinę, to jeżeli powstałe podpiramidy mają wielkość większą od 0, dla nich robisz to samo, czyli dla każdej dajesz ++result i tworzysz dwie kolejne, itd.