提出 #73262519

---

ソースコード 拡げる

import sys
from collections import deque
from heapq import heappop, heappush
from typing import List, Tuple
input = lambda: sys.stdin.readline().rstrip()
mii = lambda: map(int, input().split())
lii = lambda: list(mii())
INF = 1 << 62
class DualShortestPath:
    __slots__ = ("_n", "_g", "_min", "_hasNeg")
    def __init__(self, n: int, min: bool) -> None:
        self._n = n
        self._g = [[] for _ in range(n)]
        self._min = min
        self._hasNeg = False

    def addEdge(self, i: int, j: int, w: int) -> None:
        self._g[j].append((i, w))
        self._hasNeg |= w < 0

    def run(self) -> Tuple[List[int], bool]:
        if self._min:
            return self._spfaMin()
        return self._spfaMax() if self._hasNeg else self._dijkMax()

    def _spfaMin(self) -> Tuple[List[int], bool]:
        n, g = self._n, self._g
        dist = [-INF] * n
        dist[0] = 0
        queue = deque([0])
        count = [0] * n
        inQueue = [False] * n
        inQueue[0] = True
        count[0] = 1

        while queue:
            cur = queue.popleft()
            inQueue[cur] = False
            for next_node, weight in g[cur]:
                cand = dist[cur] + weight
                if cand > dist[next_node]:
                    dist[next_node] = cand
                    if not inQueue[next_node]:
                        count[next_node] += 1
                        if count[next_node] >= n:
                            return [], False
                        inQueue[next_node] = True
                
                        if queue and dist[next_node] > dist[queue[0]]:
                            queue.appendleft(next_node)
                        else:
                            queue.append(next_node)
        return dist, True

    def _spfaMax(self) -> Tuple[List[int], bool]:
        n, g = self._n, self._g
        dist = [INF] * n
        dist[0] = 0
        queue = deque([0])
        count = [0] * n
        inQueue = [False] * n
        inQueue[0] = True
        count[0] = 1
        while queue:
            cur = queue.popleft()
            inQueue[cur] = False
            for next_node, weight in g[cur]:
                cand = dist[cur] + weight
                if cand < dist[next_node]:
                    dist[next_node] = cand
                    if not inQueue[next_node]:
                        count[next_node] += 1
                        if count[next_node] >= n:
                            return [], False
                        inQueue[next_node] = True
                        # SLF 优化
                        if queue and dist[next_node] < dist[queue[0]]:
                            queue.appendleft(next_node)
                        else:
                            queue.append(next_node)
        return dist, True

    def _dijkMax(self) -> Tuple[List[int], bool]:
        dist = [INF] * self._n
        dist[0] = 0
        pq = [(0, 0)]
        while pq:
            curDist, cur = heappop(pq)
            if curDist > dist[cur]: continue
            for next_node, weight in self._g[cur]:
                cand = curDist + weight
                if cand < dist[next_node]:
                    dist[next_node] = cand
                    heappush(pq, (cand, next_node))
        return dist, True

def solve():
    n, k = mii()
    a = lii()
    dsp = DualShortestPath(n + 1, True)
    for i in range(1, n + 1):
        dsp.addEdge(i, 0, a[i-1])
        if i < n:
            dsp.addEdge(i, i + 1, -k)
            dsp.addEdge(i + 1, i, -k)

    dist, ok = dsp.run() 
    if ok:
        print(sum(dist[i] - a[i-1] for i in range(1, n + 1)))

t = 1
for i in range(t):
    solve()

提出情報

ジャッジ結果