W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Właśnie odwiedzasz park, w którym znajduje się wysp. Kiedy budowano park, z każdej wyspy został poprowadzony jeden most - długość mostu wychodzącego z wyspy oznaczamy przez . Łącznie w parku jest mostów. Każdym mostem można poruszać się w obu kierunkach (choć każdy most miał swój początek na jednej wyspie). Ponadto, dowolne dwie wyspy są połączone promem pływającym pomiędzy nimi w tę i z powrotem.
Ponieważ wolisz spacerować niż pływać promami, chcesz zmaksymalizować sumę długości mostów, którymi przejdziesz, stosując się do ograniczeń podanych poniżej.
Zauważ, że nie musisz odwiedzić wszystkich wysp, a przejście wszystkimi mostami może okazać się niemożliwe.
Napisz program, który mając dany opis mostów wraz z ich długościami, wyznaczy maksymalną możliwą do przejścia odległość, zgodnie z zasadami opisanymi powyżej.
- liczba wysp w parku;
- długość mostu o numerze .
Twój program powinien wczytać ze standardowego wejścia następujące dane:
Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający
jedną liczbę całkowitą - maksymalną możliwą do przejścia odległość.
UWAGA 1: Dla niektórych testów odpowiedź nie zmieści się w
32-bitowym typie całkowitym, możesz potrzebować typów int64 w Pascalu
lub long long w C/C++, aby uzyskać pełną liczbę punktów za to zadanie.
UWAGA 2: Podczas uruchamiania programów napisanych w Pascalu w środowisku
zawodów, liczby 64-bitowe są wczytywane ze standardowego wejścia znacząco wolniej
niż liczby 32-bitowe, nawet gdy wczytywane wartości i tak mieszczą się w 32 bitach.
Zalecamy wczytywanie danych do typów 32-bitowych.
W pewnych testach wartych 40 punktów, nie przekracza .
Dla danych wejściowych:
7 3 8 7 2 4 2 1 4 1 9 3 4 2 3
poprawną odpowiedzią jest:
24
mostów z przykładu to (1-3), (2-7), (3-4), (4-1), (5-1), (6-3) i (7-2).
Zauważmy, że istnieją dwa różne mosty pomiędzy wyspami 2 i 7.
Oto jedna z dróg realizujących maksymalną odległość, jaką można przejść:
Jedyną nieodwiedzoną wyspą jest 4. Zauważmy, że nie można jej już odwiedzić po pokonaniu powyższej trasy. Dokładniej: