Korniki [B]
Limit pamięci: 128 MB
Dwa korniki postanowiły zjeść stary, drewniany płot.
Płot ów składa się z sztachet, których wysokości niekoniecznie są jednakowe.
Korniki słyszały od znajomych termitów, że nic tak nie umila posiłku, jak trochę zdrowej rywalizacji.
Postanowiły zatem zagrać w grę i jeść sztachety na przemian.
Kornik w przypadającej na niego kolejce może zjeść jedną z krańcowych sztachet płotu
lub obie na raz.
Wiedząc, że każdy z korników tak wybiera sztachety, by w ciągu całej gry suma wysokości
zjedzonych przez niego sztachet była jak największa, oblicz, ile drewna przypadnie każdemu
z nich w udziale.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita (),
określająca liczbę sztachet w płocie.
Drugi wiersz zawiera ciąg liczb całkowitych (),
opisujących wysokości kolejnych sztachet.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać dwie liczby całkowite.
Pierwsza z nich określa sumę wysokości sztachet, którymi pożywi się kornik rozpoczynający
rozgrywkę, zaś druga, ile drewna przypadnie w udziale jego przeciwnikowi.
Przykład
Dla danych wejściowych:
4
5 2 9 3
poprawną odpowiedzią jest:
14 5
Wyjaśnienie do przykładu:
Pierwszy kornik w pierwszym ruchu może wybrać sztachetę o wysokości 5, o wysokości 3
lub obie na raz. Optymalnym ruchem jest zjedzenie sztachety o wysokości 5.
Przeciwnik zjada wtedy sztachety o wysokościach 2 i 3.
Autor zadania: Tomasz Idziaszek.