cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/atcoder/dp/dp_z_cht_monotone_add_max.test.py

Depends on

Code

# verification-helper: PROBLEM https://atcoder.jp/contests/dp/tasks/dp_z

def main():
    N, C = read()
    H = read()
    dp = 0
    cht = CHTMonotoneAddMax()

    for i in range(N-1):
        m = 2*H[i]
        b = -H[i]**2 + -dp
        cht.insert(m,b)
        i+=1
        dp = -cht.max(H[i]) + H[i]**2 + C

    write(dp)

from cp_library.ds.cht_monotone_add_max_cls import CHTMonotoneAddMax
from cp_library.io.read_int_fn import read
from cp_library.io.write_fn import write

if __name__ == '__main__':
    main()
# verification-helper: PROBLEM https://atcoder.jp/contests/dp/tasks/dp_z

def main():
    N, C = read()
    H = read()
    dp = 0
    cht = CHTMonotoneAddMax()

    for i in range(N-1):
        m = 2*H[i]
        b = -H[i]**2 + -dp
        cht.insert(m,b)
        i+=1
        dp = -cht.max(H[i]) + H[i]**2 + C

    write(dp)

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

from bisect import bisect_left

class CHTMonotoneAddMax:
    def __init__(self):
        self.hull = []

    def insert(self, m: int, b: int) -> None:
        # Remove lines with greater or equal slopes (maintaining monotonicity)
        while self.hull and self.hull[-1][0] >= m:
            self.hull.pop()

        def is_obsolete():
            (m1, b1), (m2, b2) = self.hull[-2], self.hull[-1]
            return (b - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m)
        
        # Remove lines that are no longer part of the lower envelope
        while len(self.hull) >= 2 and is_obsolete():
            self.hull.pop()
        
        self.hull.append((m, b))

    def max(self, x: int) -> int:
        def eval(i):
            m, b = self.hull[i]
            return m * x + b
        def key(i):
            m1, b1 = self.hull[i]
            m2, b2 = self.hull[i+1]
            return (m1-m2)*x + (b1-b2)
        return eval(bisect_left(range(len(self.hull) - 1), 0, key=key))


def read(shift=0, base=10):
    return [int(s, base) + shift for s in input().split()]
import os
import sys
from io import BytesIO, IOBase


class FastIO(IOBase):
    BUFSIZE = 8192
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        BUFSIZE = self.BUFSIZE
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        BUFSIZE = self.BUFSIZE
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)

def write(*args, **kwargs):
    '''Prints the values to a stream, or to stdout_fast by default.'''
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

if __name__ == '__main__':
    main()
Back to top page