Submission #709468

#	Time	Username	Problem	Language	Result	Execution time	Memory
709468		thanhnhanqn77	Rabbit Carrot (LMIO19_triusis)	C++14	14 / 100	1090 ms	440 KiB

triusis

#include <bits/stdc++.h>
#define fu(i, a, b) for(int i = (a); i <= (b); i++)
#define fd(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
using namespace std;
const int N = 5e3 + 5;
const int MAXA = 5005;
const int INF = 1e9 + 5;

int n;
int lim;
int a[N];


struct Segment
{
    vector<int> nodes;
    void init(int n)
    {
        nodes.resize(4 * n + 5, INF);
    }
    void update(int id, int l, int r, int u, int v, int val)
    {
        if(v < l || u > r) return;
        if(l == r) {
            nodes[id] = val;
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2, l, mid, u, v, val);
        update(id * 2 + 1, mid + 1, r, u, v, val);
        nodes[id] = min(nodes[id * 2], nodes[id * 2 + 1]);
    }
    int get(int id, int l, int r, int u, int v)
    {
        if(v < l || u > r) return INF;
        if(u <= l && r <= v) return nodes[id];
        int mid = (l + r) / 2;
        return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
};
Segment f;

ll dp[MAXA + 5];

void solve()
{
    f.init(MAXA);
    f.update(1, 1, n, 1, 1, 0);
    fu(i, 1, n)
    {
        fu(j, 1, MAXA)
        {
            int val = f.get(1, 1, MAXA, max(1, j - lim), MAXA);
            dp[j] = val + (j != a[i]);

        }
        fu(j, 1, MAXA) {
            f.update(1, 1, MAXA, j, j, dp[j]);
        }
    }
    cout << f.get(1, 1, MAXA, 1, MAXA);
}

void read()
{
    cin >> n >> lim;
    fu(i, 1, n) cin >> a[i], a[i]++;
    solve();

}

int main()
{
//    freopen("tester.inp","r",stdin);
//    freopen("tester.out","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);
    read();
}

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