제출 #1145628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145628		hirayuu_oj	3단 점프 (JOI19_jumps)	C++20	19 / 100	341 ms	589824 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin>>N;
    vector<ll> A(N);
    rep(i,N)cin>>A[i];
    vector<vector<ll>> ans(N,vector<ll>(N,-(1LL<<60)));
    rep(i,N){
        ll mx=0;
        rng(j,i+2,N){
            if((i+j)%2==0){
                mx=max(mx,A[(i+j)/2]);
            }
            ans[i][j]=A[i]+A[j]+mx;
        }
    }
    rng(i,2,N){
        rep(j,N){
            ll k=j+i;
            if(k>=N)break;
            ans[j][k]=max(ans[j][k],ans[j+1][k]);
            ans[j][k]=max(ans[j][k],ans[j][k-1]);
        }
    }
    int Q;
    cin>>Q;
    rep(i,Q){
        int L,R;
        cin>>L>>R;
        cout<<ans[L-1][R-1]<<"\n";
    }
}

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