ADACUT - Ada and Alley
As you might already know, Ada the Ladybug is a farmer. She has a long alley of trees. She wants the alley to look good so she has decided to make the heights of all trees equal. She has two possible operations: she can either cut the top of a tree, decreasing its height by one (at cost of 1) or cut the tree down (at cost of heighti).
Input
The first line of input will contain 1 ≤ N ≤ 3*105, the number of trees.
The next line will contain N integers 0 ≤ Hi ≤ 109
Output
Print the minimal cost to make the height of all trees in alley equal.
Example Input
5 1 2 3 4 5
Example Output
6
Example Input
3 1 4 2
Example Output
3
Example Input
4 1 6 1 1
Example Output
3
Example Input
6 7 11 13 1 3 5
Example Output
18
Example Input
7 1 11 4 13 5 10 7
Example Output
21
hide comments
|
dhruv2212000:
2019-03-20 10:09:54
Basic problem. Just sort and try to develop the series. All trees on right should be cut and all trees on left should be removed! AC in one go :) |
|
hodobox:
2018-12-19 03:11:16
@adhya: if you cut down the trees with heights 1,3,5,7 (this will cost you 1+3+5+7 = 16) and then shorten the 13 tree by two (costing 2), all remaining trees are now height 11, and it cost you 18 total. |
|
adhya:
2018-09-21 13:53:58
For following test case:
|
|
krunner:
2018-05-13 15:36:12
Quite interesting problem, never met with this before, only 47 lines in Java :) |
|
iampijush:
2017-12-14 16:17:46
I am getting correct answer on every given tc and also on generated random tcs from spoj toolkit. still, it says wrong answer. any clue ? Last edit: 2017-12-14 16:18:24 |
|
wisfaq:
2017-11-21 16:31:01
@julkas: Thanks |
|
julkas:
2017-11-20 19:19:35
@wisfaq Cut - 0, 11, 11, 0, 0, 0.
|
|
|
wisfaq:
2017-11-18 21:19:45
Can someone explain why:
|
|
Pranay:
2017-11-02 06:35:16
KOPC12A with modifications |
| Added by: | Morass |
| Date: | 2017-10-29 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS