結果
| 問題 | 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 | 
ソースコード
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)
            
            
            
        