#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <fstream>
#include <math.h>
#include <iomanip>
using namespace std;
#define vt vector
#define INF 0x3f3f3f3f
#define pb push_back
#define FORR1(n) for(int i = 0; i < n; i++)
#define FORR2(i,n) for(int i = 0; i < n; i++)
#define all(u) u.begin(),u.end()
typedef long long ll;
typedef vt<int> vi;
typedef pair<int,int> pii;
struct CTD{
int size;
vi par;
vt<set<int>> tree;
vi sub;
void init(vt<set<int>> &adj){
size = adj.size();
par.resize(size);
tree=adj;
sub.resize(size);
par[0] = -1;
build(0,-1);
}
void build(int u, int p) {
int n = dfs(u, p); // find the size of each subtree
int centroid = find_centroid(u, p, n); // find the centroid
par[centroid] = p;
// for each tree resulting from the removal of the centroid
set<int> ref = tree[centroid];
for (auto v : ref) {
tree[centroid].erase(v); // remove the edge to disconnect
tree[v].erase(centroid); // the component from the tree
build(v, centroid);
}
}
int dfs(int u, int p) {
sub[u] = 1;
for (auto v : tree[u])
if (v != p) sub[u] += dfs(v, u);
return sub[u];
}
int find_centroid(int node, int p, int n){
for(auto& e: tree[node]){
if(e!=p&&sub[e]>n/2){
return find_centroid(e,node,n);
}
}
return node;
}
};
struct fwtree{
int size;
vi arr;
void init(int n){
size = n;
arr.resize(n+2);
for(int i = 0; i < n+2; i++){
arr[i] = 0;
}
}
void update(int i, int x){
for(; i <= size; i+=i&-i){
arr[i]+=x;
}
}
int get(int i){
int ans = 0;
for(; i > 0; i-=i&-i){
ans+=arr[i];
}
return ans;
}
int get(int l, int r){
return get(r)-get(l-1);
}
};
struct point{
long double x, y;
};
bool operator<(point p1, point p2){
return p2.x>p1.x||(p2.x==p1.x&&p2.y>p1.y);
}
struct rect{
int left, right, top, bottom;
};
pair<int,int> get(char c){
if(c=='z'){
return {9,4};
}else if(c=='s'){
return {7,4};
}else if(c>'s'){
c--;
}
int x = int(c-'a');
return{x/3+2,x%3+1};
}
void solve(){
int n, k;
cin>>n>>k;
vi arr(n);
vi arr2(n);
for(int i = 0; i < n; i++){
cin>>arr[i];
arr2[i] = arr[i];
}
sort(all(arr2));
map<int,int> mp;
for(int i = 0; i < n; i++){
mp[arr2[i]] = i/k;
}
for(int i = 0; i < n; i++){
arr[i] = mp[arr[i]];}
int dp[n];
dp[0] = 1;
int ans = 1;
for(int i = 1; i < n; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(arr[j]<=arr[i]){
dp[i] = max(arr[i],dp[j]+1);
}
}
ans = max(ans,dp[i]);
}
cout<<n-ans<<'\n';
}
int main() {
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
588 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
612 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
