Codeforces 319C Kalila and Dimna - Implementation

Here's the full solution:

function solve(n, a, b)
    dp := array of size n+1
    dp[1] := 0
    deque := empty
    for i from 1 to n
        while deque.size ≥ 2 and dominated(deque[-2], deque[-1], (b[i], dp[i]))
            deque.pop_back()
        deque.push_back((b[i], dp[i]))
        if i < n
            while deque.size ≥ 2 and eval(deque[0], a[i+1]) ≥ eval(deque[1], a[i+1])
                deque.pop_front()
            dp[i+1] := eval(deque[0], a[i+1])
    return dp[n]

The dominated check uses cross-multiplication to avoid floating point. Each line enters and leaves the deque once.

Time complexity: $O(n)$ amortized, since each line enters and leaves the deque at most once.

Space complexity: $O(n)$ for the dp array and deque.