https://www.acmicpc.net/problem/14719
initial
this is typical trapping rainwater question
i cant Believe i couldnt solve this. I have solved it before in leetcode and i was thinking 2 pointers and tried thinking whole shit show possibilities. First i tried moving left and right together but that didnt work. Then i tried fixing one pointer and moving the other pointer closer but that didnt work. Then i tried finding out the maximum height in the given list and search the left and right region. That kinda works except when there is case of multiple same max values then it wont work. So i gave up and searched online.
For a given index, we can search the maximum left and right wall surrounding it. Then we can take the minimum of those 2 because anything taller will overflow. If the given index’s value is smaller than that minimum value, we increment answer by minVal-lst[index]. Why couldnt i think of that gosh it was easy.
revisited may 22nd
i didnt think of that solution but kinda like searching via intervals but yea needa forgot this simple logic
solution
n, m = map(int, input().split())
lst = list(map(int, input().split()))
ans = 0
for i in range(1, m - 1):
left_max = max(lst[:i])
right_max = max(lst[i + 1:])
min_max = min(left_max, right_max)
if lst[i] < min_max:
ans += min_max - lst[i]
print(ans)
complexity
n log n time cuz of max
noooooo omg it has been a while i solved coding q so fked up
outer loop goes for m-1 iterations right? and inner loop we are finding max in that sliced list. Finding the max time could be done in max m-2 iterations. So (m-1)*(m-2) is m^2 time
m space
