Submission #1013007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013007		Baytoro	Triple Jump (JOI19_jumps)	C++17	19 / 100	2426 ms	79164 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
//#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
int n,m;
const int N=1e5+5;
int dp[5005][5005];
int tree[200'005*4];
int a[200'005];
void build(int x, int l, int r) {
    if(l==r) {
        tree[x]=a[l];
        return;
    }
    int md=(l+r)/2;

    build(2*x,l,md);
    build(2*x+1,md+1,r);

    tree[x]=max(tree[2*x],tree[2*x+1]);
}

int query(int lx, int rx, int x, int l, int r) {
    if(l>rx || r<lx) return 0;
    if(lx<=l && r<=rx) return tree[x];

    int md=(l+r)/2;

    return max(query(lx,rx,2*x,l,md),query(lx,rx,2*x+1,md+1,r));
}

void sb2() {
    build(1,1,n);
    for(int j=2;j<=n;j++){
        for(int i=1;i<=n;i++) {
            if(i+j>n) break;

            dp[i][i+j]=a[i]+a[i+j]+query(i+1,(i+i+j)/2,1,1,n);

            dp[i][i+j]=max({dp[i][i+j],dp[i+1][i+j],dp[i][i+j-1]});
            //cout<<i<<' '<<i+j<<' '<<dp[i][i+j]<<endl;

        }
    }
    int q;cin>>q;
    while(q--) {
        int l,r;cin>>l>>r;
        cout<<dp[l][r]<<endl;;
    }
}
void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n<=5000) {
        sb2();
        return;
    }
    build(1,1,n);
    int q;cin>>q;
    while(q--) {
        int L,R;cin>>L>>R;
        int ans=0;
        int l=1,r=n;
        while(r-l>1) {
            int sum=a[l]+a[r]+query(l,(l+r)/2,1,1,n);
            ans=max(ans,sum);
            if(a[l]<a[r]) l++;
            else r--;
        }
        cout<<ans<<endl;
    }
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

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