Submission #495557

#TimeUsernameProblemLanguageResultExecution timeMemory
495557aris12345678Global Warming (CEOI18_glo)C++14
15 / 100
2047 ms3368 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...