Submission #713362

#	Time	Username	Problem	Language	Result	Execution time	Memory
713362		mtxas	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	1 ms	304 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    const int inf = 0x3f3f3f3f;
    int n, m;
    cin >> n >> m;
    if(n > 5000) return;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    /// calculate c
    set<int> s;
    for(int i = 1; i <= n; ++i)
    {
        s.insert(a[i]);
    }
    s.insert(0);
    s.insert(inf);
    vector<int> c {-1};
    for(auto x : s)
    {
        c.push_back(x);
    }
    int k = c.size() - 1;
    /// calc L
    vector<int> L(k + 1);
    for(int i = 1; i <= k; ++i)
    {
        for(L[i] = i; L[i] >= 1; --L[i])
        {
            if(c[i] - c[L[i]] > m) break;
        }
        L[i]++;
    }
    /// calc dp
    vector<vector<int>> dp(n + 1, vector<int> (k + 1, inf));
    assert(c[1] == 0 && (c[2] != 0));
    dp[0][1] = 0;
    vector<int> curSuff(k + 2, inf), prvSuff(k + 2, inf);
    prvSuff[1] = 0;
    for(int i = 1; i <= n; ++i)
    {
        curSuff.assign(k + 2, inf);
        for(int j = k; j >= 1; --j)
        {
            dp[i][j] = (a[i] != c[j]) + prvSuff[L[j]];
            curSuff[j] = min(curSuff[j + 1], dp[i][j]);
        }
        prvSuff = curSuff;
    }
    int ans = inf;
    for(int j = 1; j <= k ; ++j)
    {
        ans = min(ans, dp[n][j]);
    }
    cout << ans << '\n';
}
signed main()
{
    solve();
}

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