Submission #22567049

---

Source Code Expand

import sys
from heapq import *
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def main(N, A, B):
    """
    dp 関数の Fenchel 双対を slope trick で管理
    """
    INF = 1 << 60
    L = [INF]
    R = [INF]
    add_L = add_R = 0

    def push_L(x):
        heappush(L, -(x - add_L))

    def pushpop_L(x):
        return -heappushpop(L, -(x - add_L)) + add_L

    def top_L():
        return -L[0] + add_L

    def push_R(x):
        heappush(R, x - add_R)

    def pushpop_R(x):
        return heappushpop(R, x - add_R) + add_R

    def top_R():
        return R[0] + add_R

    min_f = 0
    for i in range(N):
        if i != 0:
            # dp に a|x| を加算する
            add_L -= A[i - 1]
            add_R += A[i - 1]
        c = -B[i]
        # -ax+a (-1<=x<=1) との畳み込み
        # 双対に |x-c| + c を加算する
        min_f += c

        r0 = top_R()
        min_f += max(0, c - r0)
        push_L(pushpop_R(c))
        l0 = top_L()
        min_f += max(0, l0 - c)
        push_R(pushpop_L(c))
    return -min_f

N = int(readline())
A = from_readline()
B = from_read()

print(main(N, A, B))

Submission Info

Judge Result