Solution Notes (Neal Wu): First note that "Larger umbrellas do not necessarily cost more than smaller umbrellas" is not an issue: since we are allowed to overlap umbrellas, we can precompute the minimum cost of covering any particular length (at minimum) in O(M) time.

At this point the problem simply becomes a traditional dynamic programming problem: after sorting the cows, we just need to divide them into contiguous groups, each of which we cover with an umbrella. This is a dynamic programming problem with N + 1 states (where dp[n] is the minimum cost to cover cows 1 through n); to compute each value we simply look at all possible last intervals, for an overall O(N^2 + M) algorithm. See the code below for more details.

``````
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

FILE *in = fopen ("umbrella.in", "r"), *out = fopen ("umbrella.out", "w");

const int MAXN = 5005, MAXM = 100005;

int N, M, X [MAXN], min_len_cost [MAXM];
int dp [MAXN];

int main ()
{
fscanf (in, "%d %d", &N, &M);

for (int i = 0; i < N; i++)
fscanf (in, "%d", X + i);

sort (X, X + N);

for (int i = 0; i < M; i++)
fscanf (in, "%d", min_len_cost + i);

for (int i = M - 2; i >= 0; i--)
min_len_cost [i] = min (min_len_cost [i], min_len_cost [i + 1]);

memset (dp, 63, sizeof (dp));
dp [0] = 0;

for (int n = 1; n <= N; n++)
for (int i = 0; i < n; i++)
dp [n] = min (dp [n], dp [i] + min_len_cost [X [n - 1] - X [i]]);

fprintf (out, "%d\n", dp [N]);
return 0;
}

``````