제출 #242235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242235		dwsc	3단 점프 (JOI19_jumps)	C++14	19 / 100	4083 ms	276252 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int memo[5010][5010];
int arr[5010];
int pre[5010][5010];
int n,q;
int dp(int i,int j){
    if (i+2 > j) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    int dist = (j-i)/2;
    int maxi = pre[i+1][i+dist];
    return memo[i][j] = max(arr[i]+arr[j]+maxi,max(dp(i+1,j),dp(i,j-1)));
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= n; i++){
        for (int j = i; j <= n; j++){
            pre[i][j] = max(pre[i][j-1],arr[j]);
            memo[i][j] = -1;
        }
    }
    cin >> q;
    for (int i = 0; i < q; i++){
        int l,r;
        cin >> l >> r;
        cout << dp(l,r) << "\n";
    }
}

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