#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, d;
cin >> n >> d;
vl nums;
vll memory;
for (ll i = 0; i < n; i++){
ll num;
cin >> num;
nums.push_back(num);
}
vector<multiset<ll>> dp;
for (ll i = 0; i < n; i++){
dp.push_back({});
memory.push_back({});
}
for (ll i = 0; i < n; i++){
for (ll j = n-1; j > 0; j--){
ll add;
if (!dp[j-1].empty() && *dp[j-1].begin() < nums[i]){
add = nums[i];
dp[j].insert(add);
memory[j].push_back(add);
}
else if(!dp[j].empty()){
add = *dp[j].begin();
dp[j].insert(add);
memory[j].push_back(add);
}
if (dp[j].size() > d){
dp[j].erase(dp[j].find(memory[j][memory[j].size()-d-1]));
}
}
dp[0].insert(nums[i]);
memory[0].push_back(nums[i]);
if (dp[0].size() > d){
dp[0].erase(dp[0].find(memory[0][memory[0].size()-d-1]));
}
}
ll skore = 0;
while (skore <= n && memory[skore].size() > 0){
skore++;
}
cout << skore<< "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |