Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town…

  1. User

    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 ≤ n ≤ 3 000) — the number of displays.

    The second line contains n integers s_1, s_2, …, s_n (1 ≤ s_i ≤ 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, …, c_n (1 ≤ c_i ≤ 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.

    Examples

    Input

    5 2 4 5 4 10 40 30 20 10 40

    Output

    90

    Input

    3 100 101 100 2 4 5

    Output

    -1

    Input

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

    Output

    33

    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.

  2. DeepSeek Assistant

    We need to solve: given sequences s[1..n] and c[1..n], find min c[i]+c[j]+c[k] over indices i<j<k such that s[i]<s[j]<s[k]. n up to 3000, so O(n^2) possible.

    We can brute force the middle index j. For each j, we need to find i<j with s[i]<s[j] and minimal c[i], and k>j with s[k]>s[j] and minimal c[k]. Then total = min_i + c[j] + min_k. Then overall min.

    That's O(n^2) if we compute min_i and min_k for each j in O(n) scanning. Since n=3000, O(n^2) = 9e6 which is fine. However careful: For each j, need min c[i] among i<j with s[i] < s[j]; and min c[k] among k>j with s[k] > s[j].

    We can precompute for each j these values with two loops. Or for each j, loop left and right. That's O(n^2) = 9e6 operations, absolutely fine. But we can also do O(n log n) using segment tree or something but not needed.

    Potential pitfall: values up to 1e9, but no issue.

    We'll implement: Initialize answer = INF (like a large number > 3e8 maybe 1e18). For j from 2 to n-1: left_min = INF; for i from 1 to j-1: if s[i] < s[j] and c[i] < left_min: left_min = c[i]. Similarly right_min = INF; for k from j+1 to n: if s[k] > s[j] and c[k] < right_min: right_min = c[k]. If both left_min and right_min are not INF, update ans = min(ans, left_min + c[j] + right_min).

    After loop, if ans == INF: print -1 else ans.

    Complexity O(n^2) = ~9e6 worst-case. With n=3000 it's fine.

    Edge cases: there may be multiple indices, but minimal cost.

    Test with examples: 1: s = [2,4,5,4,10]; c = [40,30,20,10,40] j=2: s=4; left: i=1 s=2<4 c=40 => left_min=40; right: k=3..5: s[3]=5>4 c=20; s[4]=4 not >; s[5]=10>4 c=40 => right_min=20; total=40+30+20=90. j=3: s=5 left: i=1 s=2<5 c=40; i=2 s=4<5 c=30 => left_min=30; right: k=4 s=4 not >; k=5 s=10>5 c=40 => right_min=40; total=30+20+40=90; j=4: s=4 left: i=1 s=2<4 c=40; i=2 s=4 not <; i=3 s=5 not < => left_min=40; right: k=5 s=10>4 c=40 => right_min=40; total=40+10+40=90; ans=90.

    2: n=3; j=2 only; s=101 left: i=1 s=100<101 c=2 => left_min=2; right: k=3 s=100 not >101 => right_min INF => no triple. ans stays INF => -1.

    3: Provided answer 33. We'll trust.

    We need to handle large INF: sum of three costs can be up to 3e8, but we can set INF = 1e18.

    Thus solution is straightforward.

    But wait: The problem states that font sizes are up to 1e9, but can be equal. We need strict inequalities: s_i < s_j < s_k. Our condition works.

    Thus answer is simple.

    But we can also implement alternative DP: dp[i][k] being min cost for increasing subsequence of length k ending at i, but that's O(n * 3) with O(n^2) maybe as well.

    But O(n^2) scanning each j is easiest.

    We must careful: The left_min we take minimal c[i] where s[i] < s[j]; but what if there are multiple i with same s? Only those strictly less count. That's fine.

    Now check complexity: For each j (max 2998) we loop i up to j-1 (max 2999) and k up to n-j (max 2999). That's roughly n^2/2 left and right each, total ~ n^2. n=3000 => ~9 million. Python is fine.

    Edge: n=3000, inner loops simple comparisons, definitely okay.

    Thus implement solve() accordingly.

    Let's write code:

    def solve(): import sys data = sys.stdin.read().split() if not data: return it = iter(data) n = int(next(it)) s = [0]*n c = [0]*n for i in range(n): s[i] = int(next(it)) for i in range(n): c[i] = int(next(it)) INF = 10**18 ans = INF for j in range(1, n-1): # 1-indexed j (from 2nd to n-1) left_min = INF sj = s[j] for i in range(j): if s[i] < sj and c[i] < left_min: left_min = c[i] if left_min == INF: continue right_min = INF for k in range(j+1, n): if s[k] > sj and c[k] < right_min: right_min = c[k] if right_min == INF: continue total = left_min + c[j] + right_min if total < ans: ans = total if ans == INF: print(-1) else: print(ans)

    That's it.

    But we need to confirm indexing: j from 1 to n-2 inclusive (0-indexed). Actually j in range(1, n-1) meaning indices 1,2,...,n-2 (0-based). For n=5, j=1,2,3? Actually n-1=4, range(1,4) gives 1,2,3. But j=3 is index 3 (fourth element) and k>j up to n-1=4 (fifth) works, i<j works. So all internal positions considered. Good.

    Now, are there any edge cases like j=0 or j=n-1? They can't be middle because need i<j<k, so j must be at least index 1 (second) and at most index n-2 (second last). So correct.

    Alternatively, we can speed up by precomputing prefix minima? But cannot because condition depends on s[j] relative. But still fine.

    Thus solution accepted.

    But there is also possibility to use binary indexed tree after coordinate compression for O(n log n) but not needed.

    Let's also test on random small cases to ensure correctness.

    We'll do a mental test: n=4, s=[1,3,2,4], c=[10,20,30,40]. Triples: (1,2,4): 10+20+40=70; (1,3,4): 1<2<4 -> 10+30+40=80. Our algorithm: j=1: s=3 left: i=0 s=1<3 c=10 -> left_min=10; right: k=2..3: k=2 s=2 not >3; k=3 s=4>3 c=40 -> right_min=40; total=10+20+40=70. j=2: s=2 left: i=0 s=1<2 c=10; i=1 s=3 not <2 -> left_min=10; right: k=3 s=4>2 c=40 -> total=10+30+40=80; min 70. Works.

    Equality not allowed: s=[1,2,2,3], c all 1. j=1 (s=2) left: i=0 s=1<2 -> left_min=1; right: k=2 s=2 not >, k=3 s=3>2 -> right_min=1 => total=1+1+1=3. But triple (0,1,3): s[0]=1< s[1]=2< s[3]=3 valid. j=2 (s=2) left: i=0 s=1<2 -> left_min=1; i=1 s=2 not <; right: k=3 s=3>2 -> right_min=1 => total=1+1+1=3 also. So answer 3. But is there triple (0,2,3)? i=0,j=2,k=3: 1<2<3 valid? s[0]=1, s[2]=2, s[3]=3, yes valid even though s[1]=2 same. So works.

    Now, is there any case where left_min and right_min both INF but still some triple exists? Suppose triple with j not being the middle? No, for any valid triple (i,j,k), j is the middle index. So if we consider all j as middle, we'll catch it. So algorithm correct.

    Thus final answer.

    Now, implement in final channel. ```python

    import sys

    def solve() -> None: data = sys.stdin.read().split() if not data: return it = iter(data) n = int(next(it)) s = [int(next(it)) for _ in range(n)] c = [int(next(it)) for _ in range(n)]

    INF = 10**18
    answer = INF
    
    # try each possible middle display j (index from 1 to n-2)
    for j in range(1, n - 1):
        sj = s[j]
        # left side: i < j and s[i] < s[j]
        left_min = INF
        for i in range(j):
            if s[i] < sj and c[i] < left_min:
                left_min = c[i]
        if left_min == INF:
            continue
    
        # right side: k > j and s[k] > s[j]
        right_min = INF
        for k in range(j + 1, n):
            if s[k] > sj and c[k] < right_min:
                right_min = c[k]
        if right_min == INF:
            continue
    
        total = left_min + c[j] + right_min
        if total < answer:
            answer = total
    
    print(-1 if answer == INF else answer)
    

    if name == "main": solve()