Submission #1096681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096681		nguyenvu	Triple Jump (JOI19_jumps)	C++14	5 / 100	4035 ms	7768 KiB

jumps

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define FILE "CHONQUA"
using namespace std;
int n,m;
ll a[500005];
ll ans=0;
ll st[500005*4];

void sub12()
{
    while(m--){
        int l,r;
        cin>>l>>r;
        for(int i=l;i<=r-2;i++){
            for(int j=i+1;j<=r-1;j++){
                for(int k=j+1;k<=r;k++){
                    if(j-i<=k-j) ans=max(ans,a[i]+a[j]+a[k]);
                }
            }
        }
        cout<<ans<<endl;
        ans=0;
    }
}

void build(int id,int l,int r)
{
    if(l==r){
        st[id]=a[l];
        return;
    }

    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    st[id]=max(st[id*2],st[id*2+1]);
}

ll get(int id,int l,int r,int u,int v)
{
    if(l>v || r<u) return -1e9;
    if(l>=u && r<=v) return st[id];

    int mid=(l+r)>>1;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

void sub34()
{
    build(1,1,n);
    while(m--){
        int l,r;
        cin>>l>>r;
        ll ans=0;
        for(int i=l;i<r;i++){
            for(int j=i+1;j<=r;j++){
                if(j*2-i<=r){
                    if(j*2-i==r) ans=max(ans,a[i]+a[j]+a[r]);
                    else {
                        ll k=get(1,1,n,j*2-i,r);
                        ans=max(ans,a[i]+a[j]+k);
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(FILE".inp","r",stdin);
    //freopen(FILE".out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    if(n<=100 && m<=100) sub12();
    else if(n<=5000) sub12();
    else if(n<=200000 && m==1) sub34();
    else sub34();
}

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