TASK_047 - AquaBlitz11's Solution

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1e18;
const int N = 1010;

int n, m, c;
ll a[N], memo[N];

ll f(int i)
{
    if (i == 0) // base case
        return 0;
    if (memo[i] != 0) // if calculated, value != 0: answer immediately
        return memo[i];

    ll ans = INF;
    for (int j = 1; j <= i; ++j)
        ans = min(ans, f(j-1) + (a[i]-a[j])*(a[i]-a[j]) + c );

    memo[i] = ans;
    return ans;
}

int main()
{
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    while (m--) {
        int q;
        scanf("%d", &q);
        printf("%lld\n", f(q));
    }

    return 0;
}