結果

問題 No.3303 Heal Slimes 2
ユーザー sasa8uyauya
提出日時 2025-10-11 12:27:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,873 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 122,428 KB
最終ジャッジ日時 2025-10-11 12:29:00
合計ジャッジ時間 77,335 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 7 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

class AVLNode:
  def __init__(self,value):
    self.value=value
    self.count=1
    self.height=1
    self.left=None
    self.right=None

class Multiset:
  def __init__(self):
    self.root=None

  def add(self,value):
    self.root=self._insert(self.root,value)

  def remove(self,value):
    self.root=self._delete(self.root,value)

  def pop(self,max=False):
    if not self.root:
      return None
    if max:
      value,self.root=self._pop_max(self.root)
    else:
      value,self.root=self._pop_min(self.root)
    return value

  def inorder(self):
    def _in(node):
      if not node:
        return []
      return _in(node.left)+[node.value]*node.count+_in(node.right)
    return _in(self.root)

  def _height(self,node):
    return node.height if node else 0

  def _update(self,node):
    node.height=1+max(self._height(node.left),self._height(node.right))

  def _balance(self,node):
    return self._height(node.left)-self._height(node.right)

  def _rotate_left(self,x):
    y=x.right
    x.right=y.left
    y.left=x
    self._update(x)
    self._update(y)
    return y

  def _rotate_right(self,y):
    x=y.left
    y.left=x.right
    x.right=y
    self._update(y)
    self._update(x)
    return x

  def _rebalance(self,node):
    self._update(node)
    b=self._balance(node)
    if b>1:
      if self._balance(node.left)<0:
        node.left=self._rotate_left(node.left)
      return self._rotate_right(node)
    if b<-1:
      if self._balance(node.right)>0:
        node.right=self._rotate_right(node.right)
      return self._rotate_left(node)
    return node

  def _insert(self,node,value):
    if not node:
      return AVLNode(value)
    if value<node.value:
      node.left=self._insert(node.left,value)
    elif value>node.value:
      node.right=self._insert(node.right,value)
    else:
      node.count+=1
      return node
    return self._rebalance(node)

  def _delete(self,node,value):
    if not node:
      return None
    if value<node.value:
      node.left=self._delete(node.left,value)
    elif value>node.value:
      node.right=self._delete(node.right,value)
    else:
      if node.count>1:
        node.count-=1
        return node
      if not node.left:
        return node.right
      if not node.right:
        return node.left
      m=node.right
      while m.left:
        m=m.left
      node.value=m.value
      node.count=m.count
      m.count=1
      node.right=self._delete(node.right,m.value)
    return self._rebalance(node)

  def _min_node(self,node):
    while node.left:
      node=node.left
    return node

  def _max_node(self,node):
    while node.right:
      node=node.right
    return node

  def _pop_min(self,node):
    if node.left:
      v,node.left=self._pop_min(node.left)
      return v,self._rebalance(node)
    else:
      if node.count>1:
        node.count-=1
        return node.value,node
      else:
        return node.value,node.right

  def _pop_max(self,node):
    if node.right:
      v,node.right=self._pop_max(node.right)
      return v,self._rebalance(node)
    else:
      if node.count>1:
        node.count-=1
        return node.value,node
      else:
        return node.value,node.left


n,K,D=map(int,input().split())
a=list(map(int,input().split()))
ans=sum(a)
X=10**10
pl=Multiset()
pl.add(-X)
pr=Multiset()
pr.add(X)
h=0
for i in range(n):
  v=a[i]
  l,r=v-D,v
  rr=pr.pop(0)
  if l<=rr:
    pr.add(rr)
    pl.add(l)
  else:
    h+=l-rr
    pl.add(rr)
    pr.add(l)
  ll=pl.pop(1)
  if ll<=r:
    pl.add(ll)
    pr.add(r)
  else:
    h+=ll-r
    pr.add(ll)
    pl.add(r)
  if i<K-1:
    continue
  ans=min(ans,h)
  v=a[i-(K-1)]
  l,r=v-D,v
  ll=pl.pop(1)
  if l<=ll:
    pl.add(ll)
    pl.remove(l)
  else:
    h-=l-ll
    pr.remove(l)
    pr.add(ll)
  rr=pr.pop(0)
  if rr<=r:
    pr.add(rr)
    pr.remove(r)
  else:
    h-=rr-r
    pl.remove(r)
    pl.add(rr)
print(ans)
0