Submission #242282

#	Time	Username	Problem	Language	Result	Execution time	Memory
242282		dantoh000	Triple Jump (JOI19_jumps)	C++14	19 / 100	570 ms	124796 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[5005];
int st[5005][14];
ll dp[5005][5005];
int q;
int query(int s, int e){
    int d = e-s+1;
    int bt = 31-__builtin_clz(d);
    int ret = max(st[s][bt],st[e-(1<<bt)+1][bt]);
    //printf("max from %d to %d is %d\n",s,e,ret);
    return ret;
}
int main(){
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%d",&a[i]);
        st[i][0] = a[i];
    }
    for (int k = 1; k < 14; k++){
        for (int i = 0; i+(1<<(k-1)) < n; i++){
            st[i][k] = max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = i+2; j < n; j++){
            int mid = (i+j)/2;
            dp[i][j]= 0ll+a[i]+a[j]+query(i+1,mid);
            //printf("<%d,%d>: %d\n",i,j,query(i+1,mid));
        }
    }
    for (int L = 2; L < n; L++){
        for (int i = 0; i+L < n; i++){
            int j = i+L;
            if (i){
                dp[i-1][j] = max(dp[i-1][j], dp[i][j]);
            }
            if (j+1 < n){
                dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
            }
        }
    }
    scanf("%d",&q);
    for (int i = 0; i < q; i++){
        int l,r;
        scanf("%d%d",&l,&r);
        --l, --r;
        printf("%lld\n",dp[l][r]);
    }

}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~
jumps.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:48: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