시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Dwa korniki postanowiły zjeść stary, drewniany płot. Płot ów składa się z n 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.
W pierwszym wierszu wejścia znajduje się liczba całkowita n (1 ≤ n ≤ 1 000 000), określająca liczbę sztachet w płocie. Drugi wiersz zawiera ciąg n liczb całkowitych hi (1 ≤ hi ≤ 1 000 000 000), opisujących wysokości kolejnych sztachet.
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.
4 5 2 9 3
14 5
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.
Contest > Algorithmic Engagements > PA 2012 6-3번