https://www.acmicpc.net/problem/14247
initial
I first thought that for each day, we sort the trees based on the height and cut down the tallest tree. But during n days, we might cut down the same tree over n over again cuz the growth rate might be really high and in just a few days, it overtakes some other trees. But that won’t give the highest optimal answer. Cutting the same tree on 2nd day and the last day won’t make a difference to our final answer because it is accumulative. In fact, we should cut the tree with highest growth rate on the last day. Cutting it on 2nd day and 6th day and last day gives the same accumulate answer as cutting it on last day.
So we sort the trees based on the growth rate and cut the tree based on ascending order of growth rate. The tree with shortest growth should be cut first because it is not worth cutting it later when we can have other options of trees that are gonna be higher in height.
solution
import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
grow = list(map(int, input().split()))
tmp = []
for i in range(n):
tmp.append((lst[i], grow[i]))
tmp.sort(key=lambda x: x[1])
ans = 0
for i in range(n):
height, growth = tmp[i][0], tmp[i][1]
ans += height + i * growth
print(ans)solution
n log n cuz of sort? n space
yes it is
