In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Nie tak dawno temu Kubuś Puchatek wybrał się z Tygryskiem popływać żaglówką. Tygrysek jest już doświadczonym żeglarzem i steruje łódką. Kubuś zaś jest szczurem lądowym, który trochę się boi. Za każdym razem, gdy zmienia się kierunek płynięcia żaglówki, zmienia się też kąt przechyłu żaglówki pod wpływem siły wiatru. Każda taka zmiana powoduje głośne wykrzyknięcie Kubusia: "czy to normalne, że są takie przechyły?". Wiadomo, im większa zmiana wychylenia łódki, tym głośniej Kubuś krzyczy, ale także ma więcej wrażeń z wakacji. Łączne wrażenia Kubusia z rejsu to suma kwadratów wszystkich zmian kątów wychylenia przy kolejnych zwrotach. Pomóż Tygryskowi je zmaksymalizować.
Rejs zaczyna się w Pięknej Górze, zaś kończy się w Sztynorcie. Zwroty można
robić tylko przy wyznaczonych bojami punktach. Wiadomo także, że z każdej boi można płynąć wyłącznie w
ściśle wyznaczonych kierunkach szlakami żeglownymi. Ponadto boje mają tę własność,
że z każdej z nich może prowadzić szlak tylko i wyłącznie do boi o numerach większych niż numer tej boi. W
Pięknej Górze, czyli miejscu startu stoi boja nr , zaś w Sztynorcie stoi boja nr
. Wiadomo, że
każdy odcinek szlaku żeglownego łączący dwie boje ma stały podany na wejściu przechył.
Wszystkie odcinki wychodzące z Pięknej Góry, a także wchodzące do Sztynortu mają przechył 0
wobec konieczności wpływania i wypływania z portu na silniku. Zakładając, że kolejno
pokonywane odcinki mają kolejne przechyły równe
, to liczba
oznacza sumaryczne wrażenia Kubusia. Twoim zadaniem jest policzyć maksymalną wartość tej sumy.
Napisz program, który:
W pierwszym wierszu znajdują się dwie liczby całkowite oraz
oddzielone pojedynczym odstępem, przy czym
, zaś
.
W każdym z kolejnych wierszy znajdują się trzy liczby całkowite
,
i
oddzielone pojedynczymi odstępami. Liczby
i
oznaczają odpowiednio numery boi
połączonych tym odcinkiem. Wiadomo, że
. Liczba
oznacza wychylenie łódki,
przy czym
. Jeśli
(Piękna Góra), bądź
(Sztynort), to
.
Powinno zawierać dokładnie jedną liczbę całkowitą oznaczającą maksymalne wrażenia Kubusia z rejsu.
Dla danych wejściowych:
6 8 1 2 0 1 3 0 2 3 10 3 4 20 4 6 0 5 6 0 4 5 10 2 5 10
poprawną odpowiedzią jest:
800
Autor zadania: Wojciech Śmietanka.