#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int INF = 1e18;
int n, x;
int a[MAXN], temp[MAXN], dp[MAXN];
int best = 0;
int lower_binary(int x)
{
int l = -1, r = n;
while(r > l + 1)
{
int m = (l + r) / 2;
if(dp[m] >= x)
{
r = m;
}
else
{
l = m;
}
}
return r;
}
int lis(int l, int r, int x)
{
int ret = 0;
for(int i = 0 ; i < n ; ++i)
{
temp[i] = a[i];
}
for(int i = l ; i <= r; ++i)
{
temp[i] += x;
}
dp[0] = -INF;
for(int i = 1 ; i <= n ; ++i)
{
dp[i] = INF;
}
for(int i = 0 ; i < n ; ++i)
{
int idx = lower_binary(temp[i]);
dp[idx] = temp[i];
ret = max(ret, idx);
}
return ret;
}
void solve()
{
cin >> n >> x;
for(int i = 0 ; i < n ; ++i)
{
cin >> a[i];
}
for(int l = 0 ; l < n ; ++l)
{
for(int r = l ; r < n ; ++r)
{
for(int k = -x ; k <= +x ; ++k)
{
best = max(best, lis(l, r, x));
}
}
}
cout << best << "\n";
}
void fastIO()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
signed main()
{
fastIO();
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |