Submission #27471515

---

Source Code Expand

from collections import defaultdict
from heapq import heappush, heappop

class DeletableMaxHeapQ():
    def __init__(self):
        self.H = []
        self.HC = defaultdict(int)
    def hpush(self, x):
        heappush(self.H, -x)
        self.HC[x] += 1
    def hpop(self):
        t = -heappop(self.H)
        while not self.HC[t]:
            t = -heappop(self.H)
        self.HC[t] -= 1
        return t
    def hmax(self):
        t = -self.H[0]
        while not self.HC[t]:
            heappop(self.H)
            t = -self.H[0]
        return t
    def hdel(self, x):
        assert self.HC[x] > 0
        self.HC[x] -= 1

class LR_trick():
    def __init__(self, n):
        self.n = n
        self.L = [i - 1 for i in range(n)]
        self.R = [i + 1 for i in range(n)]
        self.X = [1] * n
    
    def delete(self, i):
        self.X[i] = 0
    
    def left(self, i):
        i = self.L[i]
        li = []
        while i >= 0 and self.X[i] == 0:
            li.append(i)
            i = self.L[i]
        for j in li:
            self.L[j] = i
        return i
        
    def right(self, i):
        i = self.R[i]
        li = []
        while i < self.n and self.X[i] == 0:
            li.append(i)
            i = self.R[i]
        for j in li:
            self.R[j] = i
        return i
    
    def debug(self):
        print("L =", self.L)
        print("R =", self.R)
        print("X =", self.X)
    
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
if M * 2 == N:
    print(sum(A))
    exit()
if M > N - M:
    M = N - M

dh = DeletableMaxHeapQ()
lr = LR_trick(N)

for i in range(N - 2):
    x = (A[i] + A[i+1] << 20) + i
    dh.hpush(x)

ans = 0
mmm = (1 << 20) - 1
for _ in range(M):
    x = dh.hpop()
    i = x & mmm
    j = lr.right(i)
    lr.delete(i)
    lr.delete(j)
    ans += x >> 20
    l = lr.left(i)
    r = lr.right(j)
    if l >= 0:
        y = (A[l] + A[i] << 20) + l
        dh.hdel(y)
    if r < N - 1:
        y = (A[j] + A[r] << 20) + j
        dh.hdel(y)
    if 0 <= l and r < N - 1:
        y = (A[l] + A[r] << 20) + l
        dh.hpush(y)
    
print(ans)

Submission Info

Judge Result