제출 #1349546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1349546		akshar_7	Safety (NOI18_safety)	Pypy 3	66 / 100	315 ms	283164 KiB

safety

import heapq
from sys import stdin
input = stdin.readline

def main():
  #n = int(input())
  n,h = map(int, input().split())
  a = [int(i) for i in input().split()]
  #b = [int(i) for i in input().split()]
  #c = [int(i) for i in input().split()]
  #c = [list(i) for i in input().split()]
  #b = [int(i) for i in input().split()]
  #s = input().strip()
  l = [-a[0]]; r = [a[0]]
  ans = ls = rs = 0
  for i in range(1,n):
    x = a[i]
    ls -= h
    rs += h
    if -l[0]+ls > x:
      lx = -heapq.heappop(l)
      ans += abs(x-(lx+ls))
      heapq.heappush(l, -(x-ls))
      heapq.heappush(l, -(x-ls))
      heapq.heappush(r, lx+ls-rs)
    elif r[0]+rs < x:
      rx = heapq.heappop(r)
      ans += abs(x-(rx+rs))
      heapq.heappush(r, x-rs)
      heapq.heappush(r, x-rs)
      heapq.heappush(l, -(rx+rs-ls))
    else:
      heapq.heappush(l, -(x-ls))
      heapq.heappush(r, x-rs)
  return ans

T = 1#int(input())
for __ in range(T):
  print(main())

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'safety.py'...

=======
  adding: __main__.pyc (deflated 40%)

=======

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 0 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 0 / 29