#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 2e9 + 7;
int n, x;
int v[MAXN];
int dp[MAXN];
int maxiPos[MAXN], maxiNeg[MAXN];
int ans;
void bt(int cur, int sum);
int main(){
scanf("%d %d", &n, &x);
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
if(x == 1e9){
for(int j = 1; j <= n; j++)
dp[j] = INF;
for(int i = 1; i <= n; i++){
int k = lower_bound(dp, dp + 1 + n, v[i]) - dp;
dp[k] = v[i];
maxiPos[i] = max(maxiPos[i - 1], k);
ans = max(ans, k);
}
for(int j = 1; j <= n; j++)
dp[j] = INF;
dp[0] = -INF;
for(int i = n; i > 0; i--){
int k = lower_bound(dp, dp + 1 + n, -v[i]) - dp;
dp[k] = -v[i];
maxiNeg[i] = max(maxiNeg[i + 1], k);
ans = max(ans, k);
ans = max(ans, maxiPos[i] + maxiNeg[i + 1]);
}
printf("%d\n", ans);
return 0;
}
if(x == 0){
for(int j = 1; j <= n; j++)
dp[j] = INF;
for(int i = 1; i <= n; i++){
int k = lower_bound(dp, dp + 1 + n, v[i]) - dp;
dp[k] = v[i];
ans = max(ans, k);
}
printf("%d\n", ans);
return 0;
}
for(int i = n; i > 0; i--){
for(int j = 1; j <= n; j++)
dp[j] = INF;
for(int j = 1; j <= n; j++){
int k = lower_bound(dp, dp + 1 + n, v[j]) - dp;
dp[k] = v[j];
ans = max(ans, k);
}
v[i] += x;
}
printf("%d\n", ans);
}
void bt(int cur, int sum){
for(int i = 1; i <= n; i++)
dp[i] = INF;
for(int i = 1; i <= n; i++){
int k = lower_bound(dp, dp + 1 + n, v[i]) - dp;
dp[k] = v[i];
ans = max(ans, k);
}
if(cur == n) return;
v[cur + 1] += sum;
bt(cur + 1, sum);
v[cur + 1] -= sum;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &x);
~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &v[i]);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
512 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
512 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
30 ms |
380 KB |
Output is correct |
20 |
Correct |
27 ms |
384 KB |
Output is correct |
21 |
Correct |
28 ms |
504 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
24 ms |
384 KB |
Output is correct |
24 |
Correct |
24 ms |
384 KB |
Output is correct |
25 |
Correct |
23 ms |
384 KB |
Output is correct |
26 |
Correct |
32 ms |
516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
1912 KB |
Output is correct |
2 |
Correct |
55 ms |
1912 KB |
Output is correct |
3 |
Correct |
54 ms |
1912 KB |
Output is correct |
4 |
Correct |
58 ms |
1912 KB |
Output is correct |
5 |
Correct |
43 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2090 ms |
768 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
1940 KB |
Output is correct |
2 |
Correct |
33 ms |
2808 KB |
Output is correct |
3 |
Correct |
70 ms |
5496 KB |
Output is correct |
4 |
Correct |
50 ms |
4600 KB |
Output is correct |
5 |
Correct |
23 ms |
2432 KB |
Output is correct |
6 |
Correct |
40 ms |
4472 KB |
Output is correct |
7 |
Correct |
45 ms |
5112 KB |
Output is correct |
8 |
Correct |
28 ms |
2936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
512 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
30 ms |
380 KB |
Output is correct |
20 |
Correct |
27 ms |
384 KB |
Output is correct |
21 |
Correct |
28 ms |
504 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
24 ms |
384 KB |
Output is correct |
24 |
Correct |
24 ms |
384 KB |
Output is correct |
25 |
Correct |
23 ms |
384 KB |
Output is correct |
26 |
Correct |
32 ms |
516 KB |
Output is correct |
27 |
Correct |
57 ms |
1912 KB |
Output is correct |
28 |
Correct |
55 ms |
1912 KB |
Output is correct |
29 |
Correct |
54 ms |
1912 KB |
Output is correct |
30 |
Correct |
58 ms |
1912 KB |
Output is correct |
31 |
Correct |
43 ms |
2040 KB |
Output is correct |
32 |
Execution timed out |
2090 ms |
768 KB |
Time limit exceeded |
33 |
Halted |
0 ms |
0 KB |
- |