#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 LIS(vl& nums) {
vl dp;
for (int x : nums) {
auto it = std::lower_bound(dp.begin(), dp.end(), x);
if (it == dp.end())
dp.push_back(x);
else
*it = x;
}
return dp.size();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, d;
cin >> n >> d;
vl nums;
for (ll i = 0; i < n; i++){
ll num;
cin >> num;
nums.push_back(num);
}
if (d == 1){
ll maximum = 0;
ll c = 0;
for (ll i = 0; i < n; i++){
if (nums[i] > maximum){
maximum = nums[i];
c ++;
}
}
cout << c << "\n";
}
/*/else if (d == n){
cout << LIS(nums) << "\n";
}/*/
else{
vll dp;
for (ll i = 0; i < n; i++){
vl radek;
for (ll j = 0; j < n; j++){
radek.push_back(1e7);
}
dp.push_back(radek);
}
for (ll i = 0; i < n; i++){
ll num = nums[i];
ll nula = 0;
dp[0][i] = num;
for (ll j = n-1; j > 0; j--){
for (ll t = i-1; t >= max(nula, i-d); t--){
dp[j][i] = min(dp[j][i], dp[j][t]);
}
dp[j][i] = max(dp[j][i], num);
}
for (ll j = n-1; j > 0; j--){
for (ll t = i-1; t >= max(nula, i-d); t--){
if (dp[j-1][t] < num){
dp[j][i] = num;
}
}
}
}
ll skore = 1;
for (ll i = 0; i < n; i++){
if (dp[i][n-1]!= 1e7){
skore = i+1;
}
}
cout << skore;
}
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... |