Submission #1253408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253408		goldenbull	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	78 ms	12108 KiB

triusis

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using vi = vector<int>;

const char el = '\n';
const int maxn = 2e5+7;
const int inf = 1e9+7;

struct Bitcoin {
    vi arr;
    int n;
    Bitcoin (int sz) : n(sz) {
        arr.assign(sz+1, 0);
    }
    void upd(int i, int v) {
        for (; i <= n; i+= i& -i) arr[i] = max(arr[i], v);
    }
    int get(int i) {
        int res = 0;
        for (; i > 0; i-= i& -i) res = max(res, arr[i]);
        return res;
    }
};

int n, m, cnt=1;
int a[maxn];
vi b;
map<int, int> compress;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
//    freopen(".inp", "r", stdin);
//    freopen(".out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (m*i - a[i] >= 0) b.pb(m*i - a[i]);
    }

    for (auto i : b) compress[i] = 0;
    for (auto& i : compress) i.se = cnt++;
    for (auto& i : b) i = compress[i];

    Bitcoin dp(cnt);
    for (auto i : b) {
        dp.upd(i, dp.get(i) + 1);
    }
    cout << n - dp.get(cnt);

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37