Q: Динамическое программирование, алгоритм Задача такая:

Дано положительное число n, целые числа в порядке возрастания
  p1 < p2 < ... < pk, и c1,
  c2, ..., ck (0 < k < 10^5; 0 <= n, pi
  < 10^9, 0 < ci < 10^9).  pi - координаты точек
  на оси, ci - их веса. Нужно выбрать точки так, чтобы сумма
  их весов была максимальной, но расстояние между любой парой точек было
  не меньше n (n - расстояние на оси).

Я делал так - на i-м шаге для каждой точки запоминал число, равное максимальной допустимой сумме совокупности i точек с учётом их весов, расположенных по возрастанию, и оканчивающейся данной точкой.
В общем случае не работает (неверный ответ), но я не смог найти примеров с ошибкой. Помогите, пожалуйста, разобраться.

Тестовый пример (на обоих программа работает верно):


*

*Ввод
4 10
5 10 15 20
100 50 100 300

Вывод
400


*Ввод 
5 15
2 14 25 31 37
8 19 20 11 25

Вывод
44


#include <algorithm>
#include <iostream>
#include <vector>

std::vector<int> f(const std::vector<int> &first, const std::vector<int> &v1, const std::vector<int> &v2, int n1, int n2) {
    int a = -1000000000;
    std::vector<int> ans(n1);
    for (int i = 0; i != n1; ++i) {
        if (v1[i] <= n2) {
            ans[i] = a;
        } else {
            std::vector<int> A(n1);
            int j = 0;
            while (abs(v1[i] - v1[j]) > n2) {
                A[j] = first[j];
                ++j;
            }
            int m = *std::max_element(A.begin(), A.end());
            if (m == 0) {
                ans[i] = a;
            } else {
                ans[i] = m + v2[i];
            }
        }
    }
    return ans;
}

int main() {
    int n1, n2;
    std::cin >> n1 >> n2;
    std::vector<int> v1(n1);
    for (size_t i = 0; i != n1; ++i) {
        std::cin >> v1[i];
    }
    std::vector<int> v2(n1);
    for (size_t i = 0; i != n1; ++i) {
        std::cin >> v2[i];
    }
    std::vector<int> ans;
    std::vector<int> c = f(v2, v1, v2, n1, n2);
    ans.push_back(*std::max_element(c.begin(), c.end()));
    for (int i = 0; i != n1; ++i) {
        std::vector<int> x = f(c, v1, v2, n1, n2);
        ans.push_back(*std::max_element(x.begin(), x.end()))
        c = x;
    }
    std::cout << *std::max_element(ans.begin(), ans.end());
    return 0;
}


A: Учитывая, что все веса положительные, все точки удовлетворяющие вашему условию |P[i] - P[j]| < n, i # j и будут решением. Это очевидно.
