#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p1 = 27644437;
ll p2 = 1000000007;
int LIS(int n, ll a[]) {
const int INF = 1e9;
vector<int> d(n+1, INF);
d[0] = -INF;
for (int i = 0; i < n; i++) {
int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
if (d[l-1] < a[i] && a[i] < d[l])
d[l] = a[i];
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}
// int LIS(int n, ll a[]) {
// ll dp[n+1]; // dp[l] = smallest element at which a sequence of size l ends;
// int ans = 1;
// dp[1] = a[0];
// for(int i=1;i<n;i++) {
// if(dp[ans] < a[i]) {
// ans++;
// dp[ans] = a[i];
// }else if(a[i] < dp[1]) {
// dp[1] = a[i];
// }else{
// int r = ans;
// int l = 1;
// while(r - l > 1) {
// int m = (r+l)/2;
// if(a[i] < dp[m]) {
// r = m;
// }else if(a[i] >= dp[m]) {
// l = m;
// }
// }
// dp[r] = a[i];
// }
// }
// return ans;
// }
void solve() {
int n, x; cin >> n >> x;
ll a[n+1];
for(int i=0;i<n;i++) {
cin >> a[i];
}
if(x == 0) {
cout << LIS(n, a) << endl;
}else{
int ans = 1;
x=abs(x);
for(int i=0;i<n;i++) {
for(int j=i;j<n;j++) {
for(int d=-x;d<=x;d++) {
for(int k=i;k<=j;k++) {
a[k]+=d;
}
ans = max(ans, LIS(n, a));
for(int k=i;k<=j;k++) {
a[k]-=d;
}
}
}
}
cout << ans << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
// int t; cin >> t;
// while(t--)
solve();
char dksfjn;
cin >> dksfjn;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 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 |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 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 |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
29 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
55 ms |
348 KB |
Output is correct |
15 |
Correct |
22 ms |
448 KB |
Output is correct |
16 |
Correct |
38 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 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 |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
29 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
55 ms |
348 KB |
Output is correct |
15 |
Correct |
22 ms |
448 KB |
Output is correct |
16 |
Correct |
38 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Execution timed out |
2063 ms |
348 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
4688 KB |
Output is correct |
2 |
Correct |
25 ms |
4684 KB |
Output is correct |
3 |
Correct |
24 ms |
4700 KB |
Output is correct |
4 |
Correct |
24 ms |
4700 KB |
Output is correct |
5 |
Correct |
20 ms |
4116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2063 ms |
1432 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2064 ms |
2516 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 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 |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
29 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
55 ms |
348 KB |
Output is correct |
15 |
Correct |
22 ms |
448 KB |
Output is correct |
16 |
Correct |
38 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Execution timed out |
2063 ms |
348 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |