Submission #1349617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349617		akshar_7	Safety (NOI18_safety)	Pypy 3	66 / 100	376 ms	287456 KiB

safety

import heapq
from array import array
from sys import stdin
input = stdin.readline

def main():
  def get():
    nonlocal idx
    idx+=1
    return int(input_data[idx])
  input_data = stdin.read().split()
  n = int(input_data[0])
  h = int(input_data[1])
  idx = 1
  a0 = get()
  l = array('q', [-a0]); r = array('q', [a0])
  ans = ls = rs = 0
  for i in range(1,n):
    x = get()
    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