Submission #1349594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349594		akshar_7	Safety (NOI18_safety)	Pypy 3	66 / 100	365 ms	284840 KiB

safety

import heapq
from array import array
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 = array('i', [int(x) for x in input_data[2:]])
  del input_data
  l = array('q', [-a[0]]); r = array('q', [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())

Compilation message (stdout)

Compiling 'safety.py'...

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

=======

• 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