This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
#define MAXN 200000
#define MAXK 1000000000
#define MAXNUM 1000000000
int A[MAXN], INC[MAXN], DEC[MAXN];
int main() {
int K, N;
scanf("%d %d\n", &N, &K);
if ((N < 3) || (N > MAXN) || (K < 0) || (K > MAXK)) {
fprintf(stderr, "Error in input (N = %d, K = %d).\n", N, K);
return 1;
}
for (int i=0; i<N; i++) {
scanf("%d", &(A[i]));
if ((A[i] < 0) || (A[i] > MAXNUM)) {
fprintf(stderr, "Error in input (A[%d] = %d).\n", i, A[i]);
return 1;
}
}
INC[0]=1;
for (int i=1; i<N; i++) {
INC[i] = 1;
for (int j=i-1; j>=0; j--)
if (A[i] > A[j]) INC[i] = max(INC[i], 1+INC[j]);
}
DEC[N-1]=1;
for (int i=N-2; i>=0; i--) {
DEC[i] = 1;
for (int j=i+1; j<N; j++)
if (A[i] < A[j]) DEC[i] = max(DEC[i], 1+DEC[j]);
}
/*for (int i=1; i<N; i++) { INC[i] = max(INC[i], INC[i-1]); printf("%d ", INC[i]); }
printf("\n");
for (int i=N-2; i>=0; i--) { DEC[i] = max(DEC[i], DEC[i+1]); printf("%d ", DEC[i]); }
printf("\n");*/
int res = 0;
for (int i=0; i<N; i++) res = max(res, INC[i]);
if (K == 0) {
printf("%d\n", res);
return 0;
}
for (int i=0; i<N-1; i++) {
if (A[i] - A[i+1] < K) {
res = max(res, INC[i]+DEC[i+1]);
//printf("%d (%d, %d): %d (%d, %d)\n", i, A[i], A[i+1], res, INC[i], DEC[i+1]);
}
}
printf("%d\n", res);
return 0;
}
Compilation message (stderr)
glo.cpp: In function 'int main()':
glo.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d %d\n", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~
glo.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d", &(A[i]));
| ~~~~~^~~~~~~~~~~~~~~
# | 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... |