제출 #1349591

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

safety

import heapq
from sys import stdin
input = stdin.readline

def main():
  input_data = stdin.read().split()
  n = int(input_data[0])
  h = int(input_data[1])
  a = [int(x) for x in input_data[2:]]
  del input_data
  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

print(main())

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

Compiling 'safety.py'...

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

=======

• 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