Wyrównywanie terenu
Limit pamięci: 64 MB
Bajtazar postanowił wybudować dom.
Jako lokalizację dla niego wybrał pewną bardzo wąską dolinę.
Bajtazar musi najpierw wyrównać grunt pod budowę domu.
Ma on do dyspozycji dwie koparki: pierwsza z nich może zwiększyć lub zmniejszyć
poziom gruntu w dowolnym spójnym fragmencie doliny o dokładnie metrów;
druga z nich może natomiast zwiększyć lub zmniejszyć
poziom gruntu w dowolnym spójnym fragmencie doliny o dokładnie metrów.
Zauważ, że zarówno przed wykonaniem każdej takiej operacji jak i po jej wykonaniu
grunt w rozważanym kawałku doliny nie musi być równy.
Mając daną mapę terenu, wyznacz minimalną liczbę operacji, jakie
trzeba wykonać, aby wyrównać teren w całej dolinie (tj. aby grunt
w całej dolinie miał poziom równy 0).
W trakcie wykonywania ciągu operacji poziom gruntu w każdym fragmencie doliny
może być dowolnie duży lub dowolnie mały (w szczególności ujemny).
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , ,
(, ), pooddzielane pojedynczymi odstępami.
Liczba oznacza długość doliny, podaną w metrach.
Drugi wiersz zawiera liczb całkowitych nieprzekraczających
co do wartości bezwzględnej , pooddzielanych pojedynczymi odstępami.
Liczby te reprezentują poziom gruntu (wyrażony w metrach) na kolejnych kawałkach ziemi długości jednego metra.
W testach wartych 30% punktów zachodzą dodatkowe warunki oraz
.
W testach wartych 60% punktów zachodzą warunki oraz
.
W testach wartych 90% punktów zachodzi warunek .
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać
jedną liczbę całkowitą - minimalną liczbę operacji potrzebnych do wyrównania
gruntu lub liczbę , jeśli wyrównanie gruntu w dolinie za pomocą podanych
koparek nie jest w ogóle możliwe.
Przykład
Dla danych wejściowych:
5 2 3
1 2 1 1 -1
poprawną odpowiedzią jest:
5
Wyjaśnienie do przykładu:
Jedno z możliwych rozwiązań dla przykładowego wejścia to:
- zwiększ poziom gruntu na pierwszych dwóch metrach doliny o metry,
- zmniejsz poziom gruntu na pierwszych dwóch metrach doliny o metry,
- zwiększ poziom gruntu na czterech końcowych metrach doliny o metry,
- zwiększ poziom gruntu na ostatnim metrze doliny o metry,
- zmniejsz poziom gruntu na czterech końcowych metrach doliny o metry.
Autor zadania: Jakub Pachocki.