#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 500 + 10;
const int inf = 2e9;
const int mod = 998244353;
using namespace std;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,x,res = 0;
cin >> n >> x;
vector<int>a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
a[i] -= x;
}
vector<pair<int,int>>pref(n);
vector<int>v;
for(int i = 0; i < n; i++) {
if(v.empty() || v.back() < a[i]) {
v.pb(a[i]);
}else {
int lb = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
v[lb] = a[i];
}
pref[i] = {v.back(),v.size()};
}
res = pref[n - 1].S;
for(int i = 0; i < n; i++) a[i] += x;
vector<int>vec;
for(int i = n - 1; i > 0; i--) {
if(vec.empty() || vec.back() > a[i]) {
vec.pb(a[i]);
}else {
if(vec[0] < a[i]) {
vec[0] = a[i];
continue;
}
int lb = lower_bound(v.begin(),v.end(),a[i],greater<int>()) - v.begin();
v[lb] = a[i];
}
int l = 0,r = i - 1,ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(pref[mid].F < vec.back()) {
ans = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
res = max(res,(int)vec.size() + (ans != -1 ? pref[ans].S : 0));
}
cout << res;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
4956 KB |
Output is correct |
2 |
Correct |
36 ms |
6876 KB |
Output is correct |
3 |
Correct |
37 ms |
6988 KB |
Output is correct |
4 |
Correct |
36 ms |
7008 KB |
Output is correct |
5 |
Correct |
22 ms |
7388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
1624 KB |
Output is correct |
2 |
Correct |
10 ms |
2140 KB |
Output is correct |
3 |
Correct |
10 ms |
2136 KB |
Output is correct |
4 |
Incorrect |
6 ms |
2140 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
19 ms |
2832 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |