#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5005;
int n, k;
int a[N];
int b[N];
int dp[N];
unordered_map<int, int> g;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
sort(a + 1, a + 1 + n);
for (int i = 1, j = 1; i <= n; i++) {
g[a[i]] = j;
if (i % k == 0) j++;
}
int mx = 0;
for (int i = 1; i <= n; i++) {
b[i] = g[b[i]];
for (int j = i - 1; j >= 0; j--) {
if (b[i] >= b[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
mx = max(mx, dp[i]);
}
cout << n - mx;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
504 KB |
Output is correct |
2 |
Correct |
28 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
612 KB |
Output is correct |
2 |
Correct |
35 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
620 KB |
Output is correct |
2 |
Correct |
22 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
596 KB |
Output is correct |
2 |
Correct |
34 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
716 KB |
Output is correct |
2 |
Correct |
35 ms |
596 KB |
Output is correct |