Wonderful Jump (Codeforces 1768F)
Tags: Greedy, dp

You are given an array of positive integers $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$. In one operation you can jump from index $$$i$$$ to index $$$j$$$ ($$$1 \le i \le j \le n$$$) by paying $$$\min(a_i, a_{i + 1}, \ldots, a_j) \cdot (j - i)^2$$$ eris.For all $$$k$$$ from $$$1$$$ to $$$n$$$, find the minimum number of eris needed to get from index $$$1$$$ to index $$$k$$$.

Input: The first line contains a single integer $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots a_n$$$ ($$$1 \le a_i \le n$$$).

Output: Output $$$n$$$ integers — the $$$k$$$-th integer is the minimum number of eris needed to reach index $$$k$$$ if you start from index $$$1$$$.

Note: In the first example:   From $$$1$$$ to $$$1$$$: the cost is $$$0$$$,  From $$$1$$$ to $$$2$$$: $$$1 \rightarrow 2$$$ — the cost is $$$\min(2, 1) \cdot (2 - 1) ^ 2=1$$$,  From $$$1$$$ to $$$3$$$: $$$1 \rightarrow 2 \rightarrow 3$$$ — the cost is $$$\min(2, 1) \cdot (2 - 1) ^ 2 + \min(1, 3) \cdot (3 - 2) ^ 2 = 1 + 1 = 2$$$. In the fourth example from $$$1$$$ to $$$4$$$: $$$1 \rightarrow 3 \rightarrow 4$$$ — the cost is $$$\min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8$$$.

Sample Inputs:
3
2 1 3

6
1 4 1 6 3 2

2
1 2

4
1 4 4 4

Sample Outputs:
0 1 2

0 1 2 3 6 8

0 1

0 1 4 8

Solution (Python):
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    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):
        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):
        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):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())
from bisect import *
from heapq import *
from collections import *
from functools import *
from itertools import *
from time import *
from random import *
from math import log, gcd, sqrt, ceil
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def solve(testcase):
    n = II()
    nums = LII()
    dp = [float('inf') for _ in range(n)]
    dp[0] = 0
    for i in range(n):
        dist = n // nums[i] + 1
        for j in range(i - 1, max(i - dist, 0) - 1, -1):
            dp[i] = min(dp[i], dp[j] + nums[i] * (i - j) * (i - j))
            if nums[j] <= nums[i]:
                break
        for j in range(i + 1, min(i + dist + 1, n)):
            dp[j] = min(dp[j], dp[i] + nums[i] * (i - j) * (i - j))
            if nums[j] <= nums[i]:
                break
    print(*dp)
for testcase in range(1):
    solve(testcase)

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    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):
        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):
        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):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())
from bisect import *
from heapq import *
from collections import *
from functools import *
from itertools import *
from time import *
from random import *
from math import log, gcd, sqrt, ceil
''
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def solve(testcase):
    n = II()
    nums = LII()
    dp = [float('inf') for _ in range(n)]
    dp[0] = 0
    for i in range(n):
        dist = n // nums[i] + 1
        for j in range(i - 1, max(i - dist, 0) - 1, -1):
            dp[i] = min(dp[i], dp[j] + nums[i] * (i - j) * (i - j))
            if nums[j] <= nums[i]:
                break
        for j in range(i + 1, min(i + dist + 1, n)):
            dp[j] = min(dp[j], dp[i] + nums[i] * (i - j) * (i - j))
            if nums[j] <= nums[i]:
                break
    print(*dp)
for testcase in range(1):
    solve(testcase)

Solution (Python):
import re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
from typing import *
from operator import add, xor, mul, ior, iand
import bisect
BUFSIZE = 4096
inf = float('inf')

class FastIO(IOBase):
    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):
        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):
        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):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
n = II()
nums = LII()
dp = [inf] * n
for i in range(n):
    if i == 0:
        dp[i] = 0
    for j in range(1, n // nums[i] + 1):
        if i < j:
            break
        if dp[i - j] + j * j * nums[i] < dp[i]:
            dp[i] = dp[i - j] + j * j * nums[i]
        if nums[i - j] <= nums[i]:
            break
    for j in range(1, n // nums[i] + 1):
        if i + j >= n:
            break
        if nums[i + j] <= nums[i]:
            break
        if dp[i] + j * j * nums[i] < dp[i + j]:
            dp[i + j] = dp[i] + j * j * nums[i]
print(*dp)