Submission #851070

#	Time	Username	Problem	Language	Result	Execution time	Memory
851070		overwatch9	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	6 ms	856 KiB

triusis

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxa = 5000 + 1;
struct stree {
    #define lc v*2
    #define rc v*2+1
    vector <int> tree;
    stree (int sz) {
        tree.resize(sz * 4, 1e9);
    }
    void pushup(int v) {
        tree[v] = min(tree[lc], tree[rc]);
    }
    void update(int v, int tl, int tr, int p, int val) {
        if (tl > p || tr < p)
            return;
        if (tl == tr) {
            tree[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        update(lc, tl, tm, p, val);
        update(rc, tm+1, tr, p, val);
        pushup(v);
    }
    int query(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l)
            return 1e9;
        if (tl >= l && tr <= r)
            return tree[v];
        int tm = (tl + tr) / 2;
        int a = query(lc, tl, tm, l, r);
        int b = query(rc, tm+1, tr, l, r);
        return min(a, b);
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector <int> nums(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
    }
    if (m == 0) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (nums[i] != 0)
                ans++;
        }
        cout << ans << '\n';
        return 0;
    }
    int prev = 0, curr = 1;
    vector <stree> trees(2, stree (maxa));
    vector <vector <int>> dp(2, vector <int> (maxa));
    for (int i = 0; i < maxa; i++) {
        if (i <= m && i == nums[1]) {
            dp[1][i] = 0;
            trees[1].update(1, 1, maxa, nums[1], 0);
        } else if (i <= m) {
            trees[1].update(1, 1, maxa, i, 1);
            dp[1][i] = 1;
        } else {
            dp[1][i] = 1e9;
            trees[1].update(1, 1, maxa, i, 1e9);
        }
    }
    swap(prev, curr);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < maxa; j++) {
            int a = trees[prev].query(1, 1, maxa, max(1, j-m), maxa);
            dp[curr][j] = a;
            if (nums[i] != j) {
                dp[curr][j]++;
            }
        }
        for (int j = 1; j < maxa; j++) {
            trees[curr].update(1, 1, maxa, j, dp[curr][j]);
        }
        swap(prev, curr);
    }
    int ans = 1e9;
    for (int i = 1; i < maxa; i++)
        ans = min(ans, dp[prev][i]);
    cout << ans << '\n';
}

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