https://www.acmicpc.net/problem/3020
initial
The n^2 time complexity solution is so easy but considering it was gold 5 question and the input range of 400k, it would certainly result in runtime. I tried thinking of another solution but as long as i looped over height (h) and length (n), it will cause runtime as seen in my initial attempt. I tried reducing time complexity via using dictionary but to no avail.
initial runtime
import sys
input = sys.stdin.readline
n, h = map(int, input().split())
dic = {}
i = 0.5
while i < h + 0.5:
dic[i] = 0
i += 1.0
point = 0
for _ in range(n):
val = int(input())
print(val)
if point % 2 == 0:
val += 0.5
while val <= h:
dic[val] += 1
val += 1
else:
val += 0.5
while val <= h:
dic[h - val] += 1
val += 1
point+=1
min_val = max(dic.values())
Ans = [key for key, val in dic.items() if val == min_val]
print(n- min_val, len(Ans))So i googled and
https://wooono.tistory.com/624
we can use a prefix sum, where the index (height of the wall) will store the number of obstacles that this bug need to penetrate. For down walls (walls that protrude from the bottom) and up walls, the rightmost index will accumulate the most obstacles so we accumulate them (wait but why do we need to iterate reverse way? tbc)
