結果

問題 No.3303 Heal Slimes 2
ユーザー tassei903
提出日時 2025-10-05 15:41:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,479 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 154,076 KB
最終ジャッジ日時 2025-10-05 15:41:48
合計ジャッジ時間 15,796 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
# Binary Indexed Tree (Fenwick Tree)
# 0-indexed
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        assert 0 <= i < self.n
        i = i+1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def set(self, i, x):
        assert 0 <= i <= self.n
        self.add(i,x-self.get(i))
    def get(self, i, j):
        return self.sum(j) - self.sum(i)
    def lower_bound(self, k):# a[0],…,a[i]>kなる最小のi
        n = self.n
        x = 0
        r = 1
        while r <= n:r <<= 1
        size = r
        while size:
            if x + size <= n and self.data[x+size] <= k:
                k-=self.data[x+size]
                x += size
            size >>= 1
        return x
    def debug(self):
        res = []
        n = self.n
        for i in range(n):
            res.append(self.get(i))
        print(*res)


n, k, d = na()
h = na()

s = sorted(set([h[i] -d for i in range(n)] + [h[i] for i in range(n)]))
dic = {x:i for i, x in enumerate(s)}
m = len(s)
bitc = BIT(m)
bits = BIT(m)
bit2 = BIT(m)
p, q = 0, 0
def addr(x):
    global p, q
    idx = dic[x]
    bitc.add(idx, 1)
    bits.add(idx, x)
    q -= x
def remr(x):
    global p, q
    idx = dic[x]
    bitc.add(idx, -1)
    bits.add(idx, x)
    q += x

def addl(x):
    global p, q
    idx = dic[x]
    bitc.add(idx, 1)
    bits.add(idx, x)
    p -= 1
def reml(x):
    global p, q
    idx = dic[x]
    bitc.add(idx, -1)
    bits.add(idx, x)
    p += 1

def get(k):
    x = bitc.lower_bound(k)
    return x


def ADD(a):
    addr(a)
    addl(a-d)

def REM(a):
    remr(a)
    reml(a-d)


def query():
    idx = get(k)
    x = s[idx]
    cnt = bitc.get(0, idx)
    sum = bits.get(idx, m)
    # print(idx,x,p,q,cnt, sum, x * p + q + x * cnt + sum)
    
    return x * p + q + x * cnt + sum

for i in range(k):
    ADD(h[i])

ans = query()

for i in range(k, n):
    ADD(h[i])
    REM(h[i-k])
    ans = min(ans, query())

print(ans)
0