#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define intt long long
#define all(x) begin(x),end(x)
constexpr int sz = 2e5 + 5;
constexpr intt inf = 1E18 + 7;
int n, x, t[sz];
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> x;
for(register int i = 1; i <= n; ++i){
cin >> t[i];
}
vector<intt> dp(n+1, inf);
dp[0] = -inf;
for(register int i = 1; i <= n; ++i){
int l = upper_bound(all(dp), t[i]) - dp.begin();
if(dp[l] > t[i] && dp[l-1] < t[i]) dp[l] = t[i];
}
int ans(1);
for(register int i = 1; i <= n; ++i) if(dp[i] ^ inf) ans = i;
if(x == 0) return cout << ans << '\n', 0;
for(register int i = n; i >= 1; --i){
t[i] += x;
dp.assign(n+1, inf);
dp[0] = -inf;
for(register int j = 1; j <= n; ++j){
int l = upper_bound(all(dp), t[j]) - dp.begin();
if(dp[l] > t[j] && dp[l-1] < t[j]) dp[l] = t[j];
}
// if(dp[l] ^ inf) ans = max(ans, l);
for(register int j = ans; j <= n; ++j) if(dp[i] ^ inf) ans = max(ans, j);
}
cout << ans << '\n';
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:19:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
19 | for(register int i = 1; i <= n; ++i){
| ^
glo.cpp:27:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
27 | for(register int i = 1; i <= n; ++i){
| ^
glo.cpp:37:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
37 | for(register int i = 1; i <= n; ++i) if(dp[i] ^ inf) ans = i;
| ^
glo.cpp:42:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
42 | for(register int i = n; i >= 1; --i){
| ^
glo.cpp:50:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
50 | for(register int j = 1; j <= n; ++j){
| ^
glo.cpp:61:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
61 | for(register int j = ans; j <= n; ++j) if(dp[i] ^ inf) ans = max(ans, j);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
2652 KB |
Output is correct |
2 |
Correct |
28 ms |
2908 KB |
Output is correct |
3 |
Correct |
28 ms |
2804 KB |
Output is correct |
4 |
Correct |
26 ms |
2652 KB |
Output is correct |
5 |
Correct |
19 ms |
2648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2043 ms |
856 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2037 ms |
1624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |