Submission #242236

#	Time	Username	Problem	Language	Result	Execution time	Memory
242236		cheeheng	Triple Jump (JOI19_jumps)	C++17	19 / 100	1622 ms	203372 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

int A[500005];
int B[5005][5005];
int C[500005];
int D[5005][5005];

// {5,2,1,5,3}
// {0,1,2,3,4}

int main(){
    int N;
    scanf("%d", &N);

    for(int i = 1; i <= N; i ++){
        scanf("%d", &A[i]);
    }

    for(int i = 1; i <= N; i ++){
        int max1 = 0;
        for(int j = i+2; j <= N; j ++){
            if((j-i)&1){}
            else{
                max1 = max(A[(j+i)>>1], max1);
            }
            B[i][j-2] = A[i] + A[j] + max1;
        }
    }

    /*for(int i = 1; i <= N-2; i ++){
        for(int j = 1; j <= N-2; j ++){
            printf("%3d ", B[i][j]);
        }
        printf("\n");
    }*/

    for(int j = N-2; j >= 1; j --){
        for(int i = 1; i <= N-2; i ++){
            C[i] = max(C[i], B[j][i]);
            //printf("C[%d]=%d\n", i, C[i]);
        }
        int max1 = 0;
        for(int i = j; i <= N-2; i ++){
            max1 = max(max1, C[i]);
            D[j][i] = max1;
            //printf("D[%d][%d]=%d\n", j, i, max1);
        }
    }

    int Q;
    scanf("%d", &Q);

    while(Q --){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", D[l][r-2]);
    }

    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
jumps.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
jumps.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
jumps.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54