제출 #515546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515546		79brue	3단 점프 (JOI19_jumps)	C++14	46 / 100	4051 ms	139380 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
int arr[500002];
int DP[5002][5002];
int DPmax[5002][5002];
int sparse[500002][20];

void init(){
    for(int i=1; i<=n; i++) sparse[i][0] = arr[i];
    for(int d=1; d<20; d++){
        for(int i=1; i<=n; i++) sparse[i][d] = max(sparse[i][d-1], (i+(1<<(d-1))) > n ? 0 : sparse[i+(1<<(d-1))][d-1]);
    }
}

int query(int l, int r){
    int d = 31-__builtin_clz(r-l+1);
    return max(sparse[l][d], sparse[r-(1<<d)+1][d]);
}

void solveSmall(){
    for(int i=1; i<=n; i++){
        DPmax[i][i] = arr[i];
        for(int j=i+1; j<=n; j++){
            DPmax[i][j] = max(DPmax[i][j-1], arr[j]);
        }
    }
    for(int i=1; i<=n-2; i++) DP[i][i+2] = arr[i] + arr[i+1] + arr[i+2];
    for(int d=3; d<n; d++){
        for(int i=1; i+d<=n; i++){
            int j = i+d;
            DP[i][j] = max({DP[i][j-1], DP[i+1][j], arr[i] + arr[j] + DPmax[i+1][(i+j)/2]});
        }
    }

    scanf("%d", &q);
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", DP[l][r]);
    }
    exit(0);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);

    if(n <= 5000) solveSmall();

    init();

    scanf("%d", &q);
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);

        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        vector<pair<int, int> > vec;

        vec.push_back(make_pair(arr[r], r));
        vec.push_back(make_pair(arr[r-1], r-1));
        for(auto p: vec) pq.push(p);

        int ans = 0;
        for(int a=r-2; a>=l; a--){
            for(pair<int, int> p: vec){
                int b = p.second;
                if(b-a>1) ans = max(ans, arr[a] + arr[b] + query(a+1, (a+b)/2));
                if(b*2<=a+r) ans = max(ans, arr[a] + arr[b] + query(b*2-a, r));
            }

            pq.push(make_pair(arr[a], a));
            vec.push_back(make_pair(arr[a], a));

            if(pq.size() >= 20){
                vec.erase(find(vec.begin(), vec.end(), pq.top()));
                pq.pop();
            }
        }

        printf("%d\n", ans);
    }
}

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

jumps.cpp: In function 'void solveSmall()':
jumps.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:51:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
jumps.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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