umbrellas for cows

umbrellas.cpp

//http://coj.uci.cu/24h/problem.xhtml?abb=1962
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int memo[50005];
int cache[50005];
int cows[50005];
int umbrellas[1000005];
int n, m;

//topdown
int dp(int idx) {
    if(cache[idx] != -1) return cache[idx];
    if(idx == n) cache[idx] = 0;
    int best = (1 << 30);
    for(int i = idx; i < n; i++) {
        best=min(best,dp(i+1)+umbrellas[cows[i]-cows[idx] + 1]);
        cache[idx] = best;
    }
    return cache[idx] = best;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &cows[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &umbrellas[i]);
    sort(cows, cows + n);
    for(int i = 0; i < n; i++) memo[i] = (1 << 30);
    for(int i = 0; i < n; i++) cache[i] = -1;
    for(int i = m - 1; i > 0; i--)
        umbrellas[i] = min(umbrellas[i], umbrellas[i+1]);
    for(int i = n - 1; i >= 0; i--)
        for(int j = i; j < n; j++)
            memo[i] = min(memo[j + 1] + umbrellas[cows[j] - cows[i] + 1], memo[i]);
    //printf("%d\n",dp(0));
    printf("%d\n", memo[0]);
    return 0;
}