Polish version    English version  
  O olimpiadzie -> Zadania -> IX OI 2001/2002


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Zadanie: izo
Autor: Zbigniew Czech
Izolator

Zawody II stopnia, dzień próbny  
Plik źródłowy: izo.??? (np. pas, c, cpp)
Plik wejściowy: izo.in
Plik wyjściowy: izo.out

Firma Izomax produkuje wielowarstwowe izolatory cieplne. Każda z i warstw, i=1, 2, ..., n, cechuje się dodatnim współczynnikiem izolacji ai. Warstwy są ponumerowane zgodnie z kierunkiem ucieczki ciepła.

ciepło      ->      || a1 | a2 | ... | ai | ai+1 | ... | an ||      ->     

Współczynnik izolacji całego izolatora, A, określony jest sumą współczynników izolacji jego warstw. Ponadto współczynnik A rośnie, jeśli po warstwie o niższym współczynniku izolacji występuje warstwa o wyższym współczynniku, zgodnie z wzorem:

wzór

Na przykład, współczynnik izolacji izolatora o postaci:

->     || 5 | 4 | 1 | 7 ||      ->

wynosi A = (5+4+1+7)+(7-1) = 23.

Zadanie

Napisz program, który dla zadanych współczynników izolacji warstw a1, a2, ..., an wyznacza taką kolejność warstw, dla której współczynnik izolacji A całego izolatora jest największy.

Wejście

W pierwszym wierszu pliku tekstowego izo.in zapisana jest liczba warstw n, 1 <= n <= 100000. W kolejnych n wierszach zapisane są współczynniki a1, a2, ..., an, po jednym w każdym wierszu. Współczynniki te są liczbami całkowitymi i spełniają nierówności 1 <= ai <= 10000.

Wyjście

W pierwszym i jedynym wierszu pliku tekstowego izo.out. Twój program powinien zapisać jedną liczbę całkowitą równą największej możliwej wartości współczynnika izolacji A izolatora zbudowanego z warstw o podanych współczynnikach, ułożonych w odpowiedniej kolejności.

Przykład

Dla pliku wejściowego izo.in:

4
5
4
1
7
poprawną odpowiedzią jest plik wyjściowy izo.out:
24



Wersja do druku