Submission #716127

#	Time	Username	Problem	Language	Result	Execution time	Memory
716127		vjudge1	Growing Vegetables is Fun 4 (JOI21_ho_t1)	Cpython 3	0 / 100	1074 ms	3284 KiB

Main

n = int(input())
ai = input()
# n = 8
# ai = "12 2 34 85 4 91 29 85"
ml = []

def generate_ml():
  final = []
  for i in ai.split(" "):
    final.append(int(i))
  return final
ml = generate_ml()

def increase(ai_list, r, l, amount):
  for i in range(r, l+1):
    ai_list[i] += amount

def broaden(left, right, ai_list):
  while (left > 0) and (ai_list[left-1] < ai_list[left]):
    left -= 1
  while (right < len(ai_list)-1) and (ai_list[right] > ai_list[right+1]):
    right += 1
  return [left, right]


def focus(ai_list, focus):
  total = 0
  b = [focus, focus]
  b = broaden(b[0], b[1], ml)
  while (b != [0, n-1]):
    
    if (b[0] == 0):
      left_side = 10**10
    else:
      left_side = ai_list[b[0]-1] - ai_list[b[0]]
    if (b[1] == n-1):
      right_side = 10**10
    else:
      right_side = ai_list[b[1]+1] - ai_list[b[1]]
    amount = min(left_side, right_side) + 1
    total += amount
    increase(ai_list, b[0], b[1], amount)
    b = broaden(b[0], b[1], ai_list)

  return total

def main():
  main_list = generate_ml()
  min = focus(main_list, 0)
  for i in range(1, n):
    main_list = generate_ml()
    count = focus(main_list, i)
    if count<min:
      min = count
  print(min)
main()
  
    

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