제출 #242304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242304		tqbfjotld	3단 점프 (JOI19_jumps)	C++14	5 / 100	4072 ms	204664 KiB

jumps

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

long long arr[500005];
long long memo[5005][5005];

struct node{
    int s,e;
    long long v;
    node *l,*r;
    node(int _s, int _e){
    s = _s;
    e = _e;
    if (s==e) v = arr[s];
    else{
        l = new node(s,(s+e)/2);
        r = new node((s+e)/2+1,e);
        v = max(l->v,r->v);
    }
    }
    long long qu(int a, int b){
        if (b<a) return -99999999999999LL;
        if (a<=s && e<=b) return v;
        if (a<=(s+e)/2) return l->qu(a,b);
        if (b>(s+e)/2) return r->qu(a,b);
        return max(l->qu(a,b),r->qu(a,b));
    }
}*root;

int main(){
    int n,q;
    scanf("%d",&n);
    for (int x = 0; x<n; x++){
        scanf("%lld",&arr[x]);
    }
    scanf("%d",&q);
    if (n<=100 && q<=100){
        for (int x = 0; x<q; x++){
            int l,r;
            scanf("%d%d",&l,&r);
            l--;r--;
            long long ans = 0;
            for (int a = l; a<=r; a++){
                for (int c = a+2; c<=r; c++){
                    for (int b = a+1; c-b>=b-a; b++){
                        ans = max(ans,arr[a]+arr[b]+arr[c]);
                    }
                }
            }
            printf("%lld\n",ans);
        }
    }
    else{
        root = new node(0,n);
        for (int x = 0; x<n; x++){
            for (int y = 0; y<n; y++){
                memo[x][y] = root->qu(x+1,(x+y)/2) + arr[x]+arr[y];
            }
        }
        for (int x = 0; x<n; x++){
            for (int y = 1; y<n; y++){
                memo[x][y] = max(memo[x][y],memo[x][y-1]);
            }
        }
        for (int x = n-1; x>0; x--){
            for (int y = 0; y<n; y++){
                memo[x][y] = max(memo[x][y],memo[x+1][y]);
            }
        }
        for (int x = 0; x<q; x++){
            int l,r;
            scanf("%d%d",&l,&r);
            l--;r--;
            printf("%lld\n",memo[l][r]);
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int main()':
jumps.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~
jumps.cpp:72:18: 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: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54