Submission #548878

#	Time	Username	Problem	Language	Result	Execution time	Memory
548878		beaconmc	Growing Vegetables is Fun 4 (JOI21_ho_t1)	Pypy 3	100 / 100	130 ms	47756 KiB

Main

n = int(input())
lis = list(map(int, input().split()))
suslis = list(lis)
fwd = [0 for i in range(n)]
bkwd = [0 for i in range(n)]

cur = 0
for i in range(1,n):
    if lis[i]+cur <= lis[i-1]:
        cur = lis[i-1] - lis[i] + 1
    lis[i] += cur
    fwd[i] = cur

lis = list(suslis)
cur = 0
for i in range(n-2, -1, -1):
    if lis[i]+cur <= lis[i+1]:
        cur = lis[i+1] - lis[i] + 1
    lis[i] += cur
    bkwd[i] = cur
ans = float("inf")
for i in range(n):
    ans = min(ans, max(fwd[i], bkwd[i]))
print(ans)

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60