77. Problemas de internet
Autor: Pablo Ariel Heiber
Limite de tiempo : 3 seg. Total runs : 0 Aceptados : 0
El gobierno planea proporcionar Internet a personas en áreas remotas, en este caso, pequeñas ciudades que se desarrollaron al lado de una carretera larga y concurrida. Hay N pueblos ubicados uno al lado del otro a lo largo de la carretera, cada uno ocupando exactamente un kilómetro de carretera. Las ciudades se numeran consecutivamente a lo largo de la carretera de 1 a N . Para proporcionar una conexión a Internet, el gobierno colocará estaciones de punto de acceso con enlaces satelitales, que proporcionarán conexiones por cable para las ciudades.
Las estaciones se colocarán en una o más ciudades diferentes, siendo B el costo para construir cada estación. Como el gobierno quiere brindar un servicio extremadamente bueno, cada casa estará conectada directamente a una de estas estaciones. Al conectar una casa en la ciudad i , debemos elegir una estación en la ciudad j para conectar esa casa. El costo de conexión es entonces
i - j
* C , donde C es el costo de un kilómetro de cable. Tenga en cuenta que el costo del cable dentro de la ciudad es lo suficientemente pequeño como para ser ignorado, por lo que, en particular, las casas en una ciudad donde se ubica una estación no incurren en ningún costo de cableado cuando se conecta a esa estación.
Dado N , B , C y el número de casas en cada ciudad, escriba un programa para determinar el costo total mínimo de proporcionar una conexión a Internet para cada casa en cada ciudad, incluido el costo de construir las estaciones y colocar el cableado para cada casa . Debido a que el gobierno aún no ha decidido el número final de estaciones de puntos de acceso que se construirán, debe calcular el costo mínimo cuando hay 1, 2,. . . , N estaciones.
Entrada
La primera línea contiene tres enteros N , B y C que representan el número de ciudades, el costo de construir una estación de punto de acceso y el costo de un kilómetro de cable, respectivamente (1 ≤ N ≤ 6000, 1 ≤ B ≤ 10 9 y 1 ≤ C ≤ 100). La segunda línea contiene N enteros H 1 , H 2 ,. . . , H N , donde H i representa el número de casas en la i -ésima ciudad (1 ≤ H i ≤ 10 9 para i = 1, 2,...,N )
Salida
Genere una línea con N enteros que represente el costo total mínimo de proporcionar una conexión a Internet para cada casa en cada ciudad al construir 1, 2,. . . , N estaciones de punto de acceso.
Ejemplo Entrada
5 6 1
1 2 3 4 5
6 8 1
9 10 3 2 7 6
Ejemplo Salida
21 20 22 25 30
69 36 35 37 42 48