#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> st;
void update(int pos, int val, int node=1, int tl=0, int tr=n-1){
if (tl == tr){
st[node] = val;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) update(pos, val, node*2, tl, tm);
else update(pos, val, node*2+1, tm+1, tr);
st[node] = max(st[node*2], st[node*2+1]);
}
int query(int l, int r, int node=1, int tl=0, int tr=n-1){
if (l <= tl && tr <= r) return st[node];
int tm = (tl+tr)/2;
int res = 0;
if (l <= tm) res = max(res, query(l, r, node*2, tl, tm));
if (tm+1 <= r) res = max(res, query(l, r, node*2+1, tm+1, tr));
return res;
}
int main(){
int x;
cin >> n >> x;
vector<int> v(n);
for (int i=0; i<n; i++) cin >> v[i];
st.resize(4*n, 0);
vector<pair<int,int>> p(n);
for (int i=0; i<n; i++) p[i] = {v[i], -i};
sort(p.begin(), p.end());
for (int i=n-1; i>=0; i--){
int j = -p[i].second;
int bsf = query(j, n-1);
update(j, bsf+1);
}
int res = st[1];
if (x == 0){
cout << res << "\n";
return 0;
}
for (int i=0; i<n; i++){
for (int j=i; j<n; j++){
for (int k=-x; k<=x; k++){
if (k == 0) continue;
for (int l=0; l<n; l++){
if (i <= l && l <= j) p[l] = {v[l]+k, -l};
else p[l] = {v[l], -l};
}
sort(p.begin(), p.end());
for (int l=0; l<4*n; l++) st[l] = 0;
for (int l=n-1; l>=0; l--){
int m = -p[l].second;
int bsf = query(m, n-1);
update(m, bsf+1);
}
res = max(res, st[1]);
}
}
}
cout << res << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
121 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
377 ms |
348 KB |
Output is correct |
15 |
Correct |
150 ms |
348 KB |
Output is correct |
16 |
Correct |
143 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
121 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
377 ms |
348 KB |
Output is correct |
15 |
Correct |
150 ms |
348 KB |
Output is correct |
16 |
Correct |
143 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Execution timed out |
2099 ms |
344 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
5716 KB |
Output is correct |
2 |
Correct |
125 ms |
5712 KB |
Output is correct |
3 |
Correct |
119 ms |
5716 KB |
Output is correct |
4 |
Correct |
119 ms |
5712 KB |
Output is correct |
5 |
Correct |
82 ms |
5712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2064 ms |
1628 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2052 ms |
3156 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
121 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
377 ms |
348 KB |
Output is correct |
15 |
Correct |
150 ms |
348 KB |
Output is correct |
16 |
Correct |
143 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Execution timed out |
2099 ms |
344 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |