Aislador


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

La compañía Insumax produce aisladores térmicos multicapas. Cada una de las i capas, i = 1, 2,..., n de un aislador está caracterizada por un coeficiente de aislamiento a(i) positivo. Las capas están numeradas acorde a la dirección de la fuga del calor.

calor \rightarrow || a(1) | a(2) | ... | a(i) | a(i+1) | a(n) || \rightarrow

El coeficiente de aislamiento del aislador completo, A, es descrito por la suma de los coeficientes de aislamiento de sus capas. Además, el coeficiente A se eleva si una capa, con un coeficiente de aislamiento más pequeño es seguida por una capa con un coeficiente de aislamiento más grande, acorde a la fórmula:

\displaystyle A = \sum_{i=1}^n a(i) + \sum_{i=1}^{n-1} \max (0,   a(i+1)  -  a(i))

Por ejemplo, el coeficiente de aislamiento del aislador de la forma

\rightarrow || 5 | 4 | 1 | 7 || \rightarrow es A = (5  +  4  +  1  +  7)  +  (7  -  1)  =  23

Tarea

Escriba un programa el cual, para el coeficiente de aislamiento dado de las capas a(1), a(2), ..., a(n), determine un ordenamiento de las capas tal que el coeficiente de aislamiento del aislador completo sea maximizado.

Entrada

En la primera línea está el número de capas N, 1 \le N \le 100,000. En las sucesivas N líneas hay coeficientes a(1), a(2), ..., a(n), uno por línea. Estos coeficientes son enteros que satisfacen la desigualdad 1 \le a(i) \le 10,000.

Salida

En la primera y única línea tu programa debe escribir un entero igual al valor más grande posible del coeficiente de aislamiento A del aislador construido con las capas de coeficientes dadas, puestas en un orden particular.

Ejemplo de Entrada

4
5
4
1
7

Ejemplo de Salida

24

Comments


  • 0
    CarlosJavier  commented on Feb. 18, 2022, 4:50 p.m.

    El caso de prueba al hacerlo a mano me da 23 y dice ahi q tiene q ser 24, ayuda ahi porfavor.


    • 1
      josed  commented on Feb. 18, 2022, 10:22 p.m.

      Tal vez no has entendido bien el problema. Hay un orden para el que A es 24, el orden en que vienen en la entrada no es el óptimo.