提出 #76914173

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 1, -1000000000) {}

    void update(int idx, int val) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] = max(bit[idx], val);
    }

    int query(int idx) {
        int res = -1000000000;
        for (; idx > 0; idx -= idx & -idx)
            res = max(res, bit[idx]);
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    vector<long long> H(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> H[i];
    }

    long long c = K - 1;

    vector<long long> V(N + 1);
    for (int i = 1; i <= N; i++) {
        V[i] = H[i] + 1LL * i * c;
    }

    if (V[N] < V[1]) {
        cout << -1 << '\n';
        return 0;
    }

    vector<long long> vals;
    vals.reserve(N);

    for (int i = 1; i <= N; i++) {
        if (V[i] >= V[1] && V[i] <= V[N])
            vals.push_back(V[i]);
    }

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    Fenwick fw((int)vals.size());

    auto getId = [&](long long x) {
        return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
    };

    vector<int> dp(N + 1, -1000000000);

    dp[1] = 1;
    fw.update(getId(V[1]), 1);

    for (int i = 2; i <= N; i++) {
        if (V[i] < V[1] || V[i] > V[N]) continue;

        int id = getId(V[i]);
        int best = fw.query(id);

        if (best > -1000000000) {
            dp[i] = best + 1;
            fw.update(id, dp[i]);
        }
    }

    int kept = dp[N];
    if (kept < 0) {
        cout << -1 << '\n';
        return 0;
    }

    cout << (N - kept) << '\n';
    return 0;
}

提出情報

ジャッジ結果