#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef unsigned long long ll;
typedef double D;
const ll inf=(1ll<<61);
const ll mod=1e9+7;
const int MX=5009;
short int n,k;
short int a[MX];
short int dp[MX][MX];
short int DP(int x,int y){
if(x==n)return 0;
short int &ret=dp[x][y];if(ret!=-1)return ret;
ret=DP(x+1,y);
short int x1=1;
if(a[x]>=y)x1+=DP(x+1,a[x]),ret=max(ret,x1);
return ret;
}
map<int,int>hashy;
short int b[MX];
int main(){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i],b[i]=a[i];
sort(b,b+n);
for(int i=0;i<n;i++){
hashy[b[i]]=i/k;
}
for(int i=0;i<n;i++)a[i]=hashy[a[i]];
for(int i=0;i<MX;i++){
for(int j=0;j<MX;j++){
dp[i][j]=-1;
}
}
cout<<n-DP(0,0)<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
47 ms |
49400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
49504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
46 ms |
49504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
47 ms |
49728 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
58 ms |
49740 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
49 ms |
49820 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
50 ms |
49896 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
49 ms |
49992 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
49 ms |
49992 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
47 ms |
49992 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |