Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- typedef long long ll;
- struct x {
- ll coord; // координата
- ll p; // предок (по умолчанию -1)
- ll vc; // мин кол-во великов
- };
- int main() {
- ll n, k;
- std::cin >> n >> k;
- std::vector<x> xs(n);
- for (ll i = 0; i < n; i++) {
- std::cin >> xs[i].coord;
- xs[i].p = -1;
- xs[i].vc = -1;
- }
- xs[0].p = 0;
- xs[0].vc = 0;
- for (ll i = 0; i < n; i++) {
- if (xs[i].p != -1) {
- for (ll j = i + 1; (j < n) and (xs[i].coord + k >= xs[j].coord); j++) {
- if (xs[j].p == -1 or xs[j].vc > xs[i].vc + 1) {
- xs[j].p = i;
- xs[j].vc = xs[i].vc + 1;
- }
- }
- }
- }
- std::cout << xs[n-1].vc << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement