Three displays (Codeforces 987C)
Tags: Implement, dp

It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.There are $$$n$$$ displays placed along a road, and the $$$i$$$-th of them can display a text with font size $$$s_i$$$ only. Maria Stepanovna wants to rent such three displays with indices $$$i < j < k$$$ that the font size increases if you move along the road in a particular direction. Namely, the condition $$$s_i < s_j < s_k$$$ should be held.The rent cost is for the $$$i$$$-th display is $$$c_i$$$. Please determine the smallest cost Maria Stepanovna should pay.

Input: The first line contains a single integer $$$n$$$ ($$$3 \le n \le 3\,000$$$) — the number of displays.The second line contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — the font sizes on the displays in the order they stand along the road.The third line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^8$$$) — the rent costs for each display.

Output: If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices $$$i < j < k$$$ such that $$$s_i < s_j < s_k$$$.

Note: In the first example you can, for example, choose displays $$$1$$$, $$$4$$$ and $$$5$$$, because $$$s_1 < s_4 < s_5$$$ ($$$2 < 4 < 10$$$), and the rent cost is $$$40 + 10 + 40 = 90$$$.In the second example you can't select a valid triple of indices, so the answer is -1.

Sample Inputs:
5
2 4 5 4 10
40 30 20 10 40

3
100 101 100
2 4 5

10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13

Sample Outputs:
90

-1

33

Solution (Python):
from operator import __gt__, __lt__

def helper(op):
    xx = list(map(float, input().split()))
    (le, ri, a) = ([], [], xx[0])
    for b in xx:
        if a > b:
            a = b
        le.append(a)
    for a in reversed(xx):
        if op(b, a):
            b = a
        ri.append(b)
    ri.reverse()
    return (xx, le, ri)
(n, res) = (int(input()), 9000000000.0)
(ss, sLe, sRi) = helper(__lt__)
(cc, cLe, cRi) = helper(__gt__)
for j in sorted(range(1, n - 1), key=cc.__getitem__):
    (s, c) = (ss[j], cc[j])
    if cLe[j - 1] + c + cRi[j + 1] < res and sLe[j - 1] < s < sRi[j + 1]:
        a = b = 9000000000.0
        for i in range(j):
            if ss[i] < s and a > cc[i]:
                a = cc[i]
        for k in range(j + 1, n):
            if s < ss[k] and b > cc[k]:
                b = cc[k]
        if res > a + b + c:
            res = a + b + c
print(int(res) if res < 9000000000.0 else -1)

Solution (Python):
from operator import __gt__, __lt__

def helper(op):
    xx = list(map(float, input().split()))
    (le, ri, a) = ([], [], xx[0])
    for b in xx:
        if a > b:
            a = b
        le.append(a)
    for a in reversed(xx):
        if op(b, a):
            b = a
        ri.append(b)
    ri.reverse()
    return (xx, le, ri)
(n, res) = (int(input()), 9000000000.0)
(ss, sLe, sRi) = helper(__lt__)
(cc, cLe, cRi) = helper(__gt__)
for j in sorted(range(1, n - 1), key=cc.__getitem__):
    (s, c) = (ss[j], cc[j])
    if cLe[j - 1] + c + cRi[j + 1] < res and sLe[j - 1] < s < sRi[j + 1]:
        a = b = 9000000000.0
        for i in range(j):
            if ss[i] < s and a > cc[i]:
                a = cc[i]
        for k in range(j + 1, n):
            if s < ss[k] and b > cc[k]:
                b = cc[k]
        if res > a + b + c:
            res = a + b + c
print(int(res) if res < 9000000000.0 else -1)

Solution (Python):
import math

def getIntList():
    return list(map(int, input().split()))
n = int(input())
s = getIntList()
c = getIntList()
maxValue = 10 ** 8 + 1
result = maxValue * 3
minLeft = [0] * n
minRight = [0] * n
minLeft[0] = c[0]
for i in range(1, n):
    minLeft[i] = min(c[i], minLeft[i - 1])
minRight[n - 1] = c[n - 1]
for i in range(n - 2, -1, -1):
    minRight[i] = min(c[i], minRight[i + 1])
minSLeft = [0] * n
maxSRight = [0] * n
minSLeft[0] = s[0]
for i in range(1, n):
    minSLeft[i] = min(s[i], minSLeft[i - 1])
maxSRight[n - 1] = s[n - 1]
for i in range(n - 2, -1, -1):
    maxSRight[i] = max(s[i], maxSRight[i + 1])
prices = [(c[j], j) for j in range(1, n - 1)]
prices.sort()
for (k, j) in prices:
    if minLeft[j - 1] + c[j] + minRight[j + 1] >= result:
        continue
    if minSLeft[j - 1] >= s[j] or s[j] >= maxSRight[j + 1]:
        continue
    a = maxValue
    for i in range(j):
        if s[i] < s[j]:
            a = min(a, c[i])
    b = maxValue
    for k in range(j + 1, n):
        if s[j] < s[k]:
            b = min(b, c[k])
    curr = a + b + c[j]
    result = min(result, curr)
if result == maxValue * 3:
    result = -1
print(result)