Submission #1013009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013009		Aiperiii	Triple Jump (JOI19_jumps)	C++14	19 / 100	4065 ms	201424 KiB

jumps

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
int ans[5005][5005];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
        vector <int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-2;i++){
        int mx=a[i+1];
        vector <int> v;v.pb(a[i+1]);
        for(int j=i+2;j<n;j++){
            int sum=a[j]+a[i];
            mx=max(mx,a[j]);
            v.pb(mx);
            ans[i][j]=sum+v[v.size()/2-1];
        }
       
    }
    
    for(int i=0;i<n;i++){
        int pr=0;
        for(int j=0;j<n;j++){
            ans[i][j]=max(ans[i][j],pr);
            pr=ans[i][j];
        }
    }
   
    for(int j=0;j<n;j++){
        int pr=0;
        for(int i=n-1;i>=0;i--){
            ans[i][j]=max(ans[i][j],pr);
            pr=ans[i][j];
        }
    }
    
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;r--;
        cout<<ans[l][r]<<"\n";
    }
}



/*
 5
 5 2 1 5 3
 3
 1 4
 2 5
 1 5

 */

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