제출 #615326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
615326		AbdelmagedNour	3단 점프 (JOI19_jumps)	C++17	19 / 100	353 ms	77192 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int sp[13][N],dp[N][N];
void build(int n){
    for(int j=1;j<13;j++){
        for(int i=0;i+(1<<j)<=n;i++){
            sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
        }
    }
}
int RMQ(int l,int r){
    int sz=__lg(r-l+1);
    return max(sp[sz][l],sp[sz][r-(1<<sz)+1]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>sp[0][i];
    build(n);
    for(int sz=2;sz<n;sz++){
        for(int i=0;i+sz<n;i++){
            dp[i][i+sz]=sp[0][i]+sp[0][i+sz]+RMQ(i+1,(i+sz+i)/2);
            dp[i][i+sz]=max({dp[i][i+sz],dp[i+1][i+sz],dp[i][i+sz-1]});
        }
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;r--;
        cout<<dp[l][r]<<"\n";
    }
    return 0;
}

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