제출 #1313631

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

jumps

#include <bits/stdc++.h>

#define int long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

const int N = 5e3+5 , maxn = 3e5 + 5;
const int MOD = 1e9+7;

int n , q , a[N] , mx[N][N] , ans[N][N] , suf[N][N];

void arkanefury228(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for (int l = 1; l <= n; l++){
        int m = a[l];
        for (int r = l; r <= n; r++){
            m = max(m , a[r]);
            mx[l][r] = m;
        }
    }

    for (int r = 1; r <= n; r++){
        for (int l = 1; l <= r; l++){
            if (r - l + 1 <= 2) break;
            int sum = a[r] + a[l] + mx[l + 1][(r + l) / 2];
            ans[l][r] = max(ans[l][r - 1] , sum);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = i; j >= 1; j--){
            suf[j][i] = max(ans[j][i] , suf[j + 1][i]);
        }
    }

    cin >> q;
    while(q--){
        int l , r;
        cin >> l >> r;
        cout << suf[l][r] << ent;
    }
}


signed main(){

    PRaim_bek_abi

    int t=1;
    //cin>>t;
    for (int respagold = 1; respagold <= t; respagold++) arkanefury228();
}

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