#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
int v[DIM],d[DIM];
pair <int,int> dp_left[DIM],dp_right[DIM];
int n,i,x,k,sol;
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>x;
for (i=1;i<=n;i++)
cin>>v[i];
d[1] = 1, k = 1;
dp_left[1] = make_pair(v[1],1);
for (i=2;i<=n;i++){
int st = 1, dr = k;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[d[mid]] < v[i])
st = mid+1;
else dr = mid-1;
}
if (st == k+1)
k++;
d[st] = i;
dp_left[i] = make_pair(v[d[k]],k); /// elementul cu care se termina scmaxul dintre primele i elemente
}
sol = k;
d[1] = n, k = 1;
dp_right[n] = make_pair(v[n],1);
for (i=n-1;i;i--){
int st = 1, dr = k;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[d[mid]] > v[i])
st = mid+1;
else dr = mid-1;
}
if (st == k+1)
k++;
d[st] = i;
dp_right[i] = make_pair(v[d[k]],k);
}
/// modific un sufix
for (i=1;i<n;i++){
int val = dp_left[i].first;
int val2 = dp_right[i+1].first;
if (val < val2)
sol = max (sol,dp_left[i].second + dp_right[i+1].second);
else {
int dif = val - val2 + 1;
if (dif <= x)
sol = max (sol,dp_left[i].second + dp_right[i+1].second);
}
}
/// modific un prefix
for (i=2;i<=n;i++){
int val = dp_left[i-1].first;
int val2 = dp_right[i].first;
if (val < val2)
sol = max (sol,dp_left[i-1].second + dp_right[i].second);
else {
int dif = val - val2 + 1;
if (dif <= x)
sol = max (sol,dp_left[i-1].second + dp_right[i].second);
}
}
cout<<sol;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
156 ms |
4216 KB |
Output is correct |
2 |
Correct |
154 ms |
4216 KB |
Output is correct |
3 |
Correct |
165 ms |
4216 KB |
Output is correct |
4 |
Correct |
152 ms |
4344 KB |
Output is correct |
5 |
Correct |
98 ms |
4600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
1272 KB |
Output is correct |
2 |
Correct |
41 ms |
1272 KB |
Output is correct |
3 |
Correct |
41 ms |
1272 KB |
Output is correct |
4 |
Correct |
29 ms |
1408 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
27 ms |
1400 KB |
Output is correct |
7 |
Correct |
38 ms |
1272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
78 ms |
2296 KB |
Output is correct |
2 |
Correct |
77 ms |
2296 KB |
Output is correct |
3 |
Correct |
151 ms |
4216 KB |
Output is correct |
4 |
Correct |
97 ms |
4600 KB |
Output is correct |
5 |
Correct |
50 ms |
2424 KB |
Output is correct |
6 |
Correct |
95 ms |
4472 KB |
Output is correct |
7 |
Correct |
128 ms |
4472 KB |
Output is correct |
8 |
Correct |
75 ms |
2296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |