#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n,d; cin >> n >> d;
vector<int> as(n);
for (int& i : as) cin >> i;
if (d == 1) {
int maxim = 1;
vector<int> stck;
stck.push_back(as.back());
for (int i = as.size()-2; i>=0; i--) {
while (stck.size() > 0 && stck.back() <= as[i]) stck.pop_back();
stck.push_back(as[i]);
maxim = max(maxim, (int)stck.size());
}
cout << maxim << endl;
} else if (d == n) {
vector<int> dp;
dp.push_back(as[0]);
for (int i = 1; i<n; i++) {
int l = 0;
int r = dp.size();
while (l<r) {
int m = (l+r)/2;
if (dp[m] < as[i]) {
l = m+1;
} else {
r = m;
}
}
if (l == dp.size()) {
dp.push_back(as[i]);
} else {
dp[l] = as[i];
}
}
cout << dp.size() << endl;
} else {
vector<vector<int>> dp(n, vector<int>(n+1, -1));
vector<multiset<int>> maxs(n+1);
dp[0][1] = as[0];
maxs[1].insert(as[0]);
for (int i = 1; i<n; i++) {
if (i > d) {
// Smazat i-d-1
for (int j = 0; j<n+1; j++) {
if (dp[i-d-1][j] == -1) continue;
if (maxs[j].find(dp[i-d-1][j]) != maxs[j].end()) {
maxs[j].erase(maxs[j].find(dp[i-d-1][j]));
}
}
}
dp[i][1] = as[i];
for (int j = 0; j<n+1; j++) {
if (maxs[j].size() > 0) {
int minim = *(maxs[j].begin());
if (minim < as[i]) {
if (dp[i][j+1] == -1) {
dp[i][j+1] = as[i];
} else {
dp[i][j+1] = min(dp[i][j+1], as[i]);
}
} else {
if (dp[i][j] == -1) {
dp[i][j] = minim;
} else {
dp[i][j] = min(dp[i][j], minim);
}
}
}
}
for (int j = 0; j<n+1; j++) {
if (dp[i][j] == -1) continue;
maxs[j].insert(dp[i][j]);
}
}
int maxim = 0;
for (int j = 0; j<n+1; j++) {
if (dp.back()[j] != -1) maxim = j;
}
cout << maxim << endl;
}
}
# | 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... |