#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define pque priority_queue
#define pqueg priority_queue<ll,vector<ll>,greater<ll>>
#define que queue<ll>
#define FOR(m,i,n) for(int i=(m); i<=(n); i++)
#define FORM(m,i,n) for(int i=(m); i>=(n); i--)
ll n,x,ans,temp;
ll a[200200];
map<ll,ll> memo[200200][4];
map<ll,ll> memo1[200200];
map<ll,bool> vis[200200];
ll dp(ll idx, ll stat, ll prev) {
if(idx == n + 1) return 0;
if(memo[idx][stat][prev] == 0) {
memo[idx][stat][prev] = dp(idx+1,stat,prev);
if(stat == 0) {
if(prev < a[idx]) { // ambil ga nambah
memo[idx][stat][prev] = max(memo[idx][stat][prev],
dp(idx+1,0,a[idx]) + 1);
}
if(prev < a[idx]+temp) { // ambil nambah
memo[idx][stat][prev] = max(memo[idx][stat][prev],
dp(idx+1,1,a[idx]+temp) + 1);
}
}
else if(stat == 1) {
if(prev < a[idx] + temp) { // ambil dan masih nambah
memo[idx][stat][prev] = max(memo[idx][stat][prev],
dp(idx+1,1,a[idx]+temp) + 1);
}
if(prev < a[idx]) { // ambil dah ga nambah
memo[idx][stat][prev] = max(memo[idx][stat][prev],
dp(idx+1,2,a[idx]) + 1);
}
}
else {
if(prev < a[idx]) { // ambil dah ga nambah
memo[idx][stat][prev] = max(memo[idx][stat][prev],
dp(idx+1,2,a[idx]) + 1);
}
}
}
return memo[idx][stat][prev];
}
//ll dp1(ll idx, ll prev) {
// if(idx == n+1) return 0;
// if(!vis[idx][prev]) {
// vis[idx][prev] = true;
// memo1[idx][prev] = dp1(idx+1,prev);
// if(prev < a[idx]) {
// memo1[idx][prev] = max(memo1[idx][prev],dp1(idx+1,a[idx])+1);
// }
// }
// return memo1[idx][prev];
//}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> x;
FOR(1,i,n) {
cin >> a[i];
}
// if(x == 0) {
// cout << dp1(1,-1e12) << endl;
// return 0;
// }
// else {
FOR(1,i,x*2+1) {
temp = i - (x+1);
ans = max(ans,dp(1,0,-1e12));
}
cout << ans << endl;
// }
}
/*
8 0
7 3 5 12 2 7 3 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
56660 KB |
Output is correct |
2 |
Correct |
29 ms |
56740 KB |
Output is correct |
3 |
Correct |
26 ms |
56644 KB |
Output is correct |
4 |
Correct |
26 ms |
56708 KB |
Output is correct |
5 |
Correct |
26 ms |
56660 KB |
Output is correct |
6 |
Correct |
26 ms |
56624 KB |
Output is correct |
7 |
Correct |
26 ms |
56748 KB |
Output is correct |
8 |
Correct |
25 ms |
56660 KB |
Output is correct |
9 |
Correct |
25 ms |
56660 KB |
Output is correct |
10 |
Correct |
26 ms |
56628 KB |
Output is correct |
11 |
Correct |
27 ms |
56752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
56660 KB |
Output is correct |
2 |
Correct |
29 ms |
56740 KB |
Output is correct |
3 |
Correct |
26 ms |
56644 KB |
Output is correct |
4 |
Correct |
26 ms |
56708 KB |
Output is correct |
5 |
Correct |
26 ms |
56660 KB |
Output is correct |
6 |
Correct |
26 ms |
56624 KB |
Output is correct |
7 |
Correct |
26 ms |
56748 KB |
Output is correct |
8 |
Correct |
25 ms |
56660 KB |
Output is correct |
9 |
Correct |
25 ms |
56660 KB |
Output is correct |
10 |
Correct |
26 ms |
56628 KB |
Output is correct |
11 |
Correct |
27 ms |
56752 KB |
Output is correct |
12 |
Correct |
26 ms |
56788 KB |
Output is correct |
13 |
Correct |
25 ms |
56784 KB |
Output is correct |
14 |
Correct |
26 ms |
56924 KB |
Output is correct |
15 |
Correct |
26 ms |
56804 KB |
Output is correct |
16 |
Correct |
26 ms |
56796 KB |
Output is correct |
17 |
Correct |
26 ms |
56636 KB |
Output is correct |
18 |
Correct |
26 ms |
56708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
56660 KB |
Output is correct |
2 |
Correct |
29 ms |
56740 KB |
Output is correct |
3 |
Correct |
26 ms |
56644 KB |
Output is correct |
4 |
Correct |
26 ms |
56708 KB |
Output is correct |
5 |
Correct |
26 ms |
56660 KB |
Output is correct |
6 |
Correct |
26 ms |
56624 KB |
Output is correct |
7 |
Correct |
26 ms |
56748 KB |
Output is correct |
8 |
Correct |
25 ms |
56660 KB |
Output is correct |
9 |
Correct |
25 ms |
56660 KB |
Output is correct |
10 |
Correct |
26 ms |
56628 KB |
Output is correct |
11 |
Correct |
27 ms |
56752 KB |
Output is correct |
12 |
Correct |
26 ms |
56788 KB |
Output is correct |
13 |
Correct |
25 ms |
56784 KB |
Output is correct |
14 |
Correct |
26 ms |
56924 KB |
Output is correct |
15 |
Correct |
26 ms |
56804 KB |
Output is correct |
16 |
Correct |
26 ms |
56796 KB |
Output is correct |
17 |
Correct |
26 ms |
56636 KB |
Output is correct |
18 |
Correct |
26 ms |
56708 KB |
Output is correct |
19 |
Correct |
1398 ms |
150556 KB |
Output is correct |
20 |
Correct |
881 ms |
150220 KB |
Output is correct |
21 |
Correct |
926 ms |
150248 KB |
Output is correct |
22 |
Correct |
1093 ms |
150400 KB |
Output is correct |
23 |
Correct |
337 ms |
104216 KB |
Output is correct |
24 |
Correct |
347 ms |
104124 KB |
Output is correct |
25 |
Correct |
412 ms |
107596 KB |
Output is correct |
26 |
Correct |
869 ms |
150716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1481 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1910 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1792 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
56660 KB |
Output is correct |
2 |
Correct |
29 ms |
56740 KB |
Output is correct |
3 |
Correct |
26 ms |
56644 KB |
Output is correct |
4 |
Correct |
26 ms |
56708 KB |
Output is correct |
5 |
Correct |
26 ms |
56660 KB |
Output is correct |
6 |
Correct |
26 ms |
56624 KB |
Output is correct |
7 |
Correct |
26 ms |
56748 KB |
Output is correct |
8 |
Correct |
25 ms |
56660 KB |
Output is correct |
9 |
Correct |
25 ms |
56660 KB |
Output is correct |
10 |
Correct |
26 ms |
56628 KB |
Output is correct |
11 |
Correct |
27 ms |
56752 KB |
Output is correct |
12 |
Correct |
26 ms |
56788 KB |
Output is correct |
13 |
Correct |
25 ms |
56784 KB |
Output is correct |
14 |
Correct |
26 ms |
56924 KB |
Output is correct |
15 |
Correct |
26 ms |
56804 KB |
Output is correct |
16 |
Correct |
26 ms |
56796 KB |
Output is correct |
17 |
Correct |
26 ms |
56636 KB |
Output is correct |
18 |
Correct |
26 ms |
56708 KB |
Output is correct |
19 |
Correct |
1398 ms |
150556 KB |
Output is correct |
20 |
Correct |
881 ms |
150220 KB |
Output is correct |
21 |
Correct |
926 ms |
150248 KB |
Output is correct |
22 |
Correct |
1093 ms |
150400 KB |
Output is correct |
23 |
Correct |
337 ms |
104216 KB |
Output is correct |
24 |
Correct |
347 ms |
104124 KB |
Output is correct |
25 |
Correct |
412 ms |
107596 KB |
Output is correct |
26 |
Correct |
869 ms |
150716 KB |
Output is correct |
27 |
Runtime error |
1481 ms |
262144 KB |
Execution killed with signal 9 |
28 |
Halted |
0 ms |
0 KB |
- |