Explanation

Let us define a function $f(a,b)$ which denotes the cost when we place sawmills at $a$ and $b$, $a < b$. Let $T$ be the cost of transporting all trees to the base of the hill (i.e. cost without building any sawmills). Denote two arrays $W$ and $D$ that represent the prefix sum of the weight and distance, respectively.

$f(a, b) = T - W[a] \cdot (D[b] - D[a]) - W[b] \cdot (D[n + 1] - D[b])$

If we hold $b$ as constant, we can rearrange the equation into:

Thus, $f$ can be decomposed into four parts: $y_a = T + W[a] \cdot D[a]$, $m_a = -W[a]$, $x = D[b]$, $c = -W[b] \cdot D[n + 1] + W[b] \cdot D[b]$. Thus,

Define another function $g(b)$ that denotes the minimum cost if we place the second sawmill at $b$. This can simply be expressed in terms of $f(a,b)$.

Because $x$ and $c$ are functions of $b$, we can hold them constant. Note that $y_a + m_a x$ forms a linear function of $x$. We can use the convex hull trick to efficiently query the minimum value of a group of linear functions. The answer is simply $\max_{2 \leq b \leq N}g(b)$.

The last thing that remains is to efficiently calculate $T$.

Time Complexity: $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ depending on the implementation of CHT. Because the following solution uses LineContainer, it runs in $\mathcal{O}(n \log n)$.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Line Container (Click to expand)

const int MAXN = 20000;

int N;
long long W[MAXN + 1], D[MAXN + 1], T;