1551E - Fixed Points - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

int v[6005], dp[6005][6005];

int n, k;

signed main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
            cin >> v[i];
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                dp[i][j] = 0;
            }
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + ((v[i + 1] == j + 1) ? 1 : 0));
            }
        }
        int rasp = -1;
        for(int i = n; i >= 0; i--)
        {
            if(dp[n][i] >= k)
            {
                rasp = n - i;
                break;
            }
        }
        cout << rasp << '\n';
    }
    return 0;
}