Submission #944059

#	Time	Username	Problem	Language	Result	Execution time	Memory
944059		beepbeepsheep	Triple Jump (JOI19_jumps)	C++17	0 / 100	730 ms	27276 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll maxn=2e5+5;
const ll inf=1e15;
ll arr[maxn];
struct node{
    ll s,e,m,val;
    node *l,*r;
    node (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=0;
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ll v){
        if (s==e){
            val=v;
            return;
        }
        if (x>m) r->upd(x,v);
        else l->upd(x,v);
        val=max(l->val,r->val);
    }
    ll query(ll x, ll y){
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return max(l->query(x,y),r->query(x,y));
    }
}*root;

ll ans=0;
ll n;
void dnc(ll l, ll r,ll optl, ll optr){
    //cerr<<l<<' '<<r<<' '<<optl<<' '<<optr<<endl;
    if (l>r) return;
    ll m=(l+r)>>1;
    ll opt=-1,best=0;
    for (int i=max(optl,m+1);i<=optr;i++){
        if (2*m-i<=0) break;
        ll res=arr[i]+root->query(2*m-i,m-1);
        if (res>best){
            opt=i;
            best=res;
        }
    }
    ans=max(ans,best+arr[m]);
    dnc(l,m-1,optl,opt);
    dnc(m+1,r,opt,optr);
}
void dnc2(ll l, ll r,ll optl, ll optr){
    //cerr<<l<<' '<<r<<' '<<optl<<' '<<optr<<endl;
    if (l>r) return;
    ll m=(l+r)>>1;
    ll opt=-1,best=0;
    for (int i=max(1LL,optl-5);i<=min(m-1,optr+5);i++){
        if (2*m-i>n) continue;
        ll res=arr[i]+root->query(2*m-i,n);
        if (res>best){
            opt=i;
            best=res;
        }
    }
    ans=max(ans,best+arr[m]);
    dnc2(l,m-1,optl,opt);
    dnc2(m+1,r,opt,optr);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    root=new node(1,n);
    for (int i=1;i<=n;i++) cin>>arr[i],root->upd(i,arr[i]);
    ll q,l,r;
    cin>>q;
    assert(q==1);
    cin>>l>>r;
    assert(l==1 && r==n);
    dnc(2,n-1,1,n);
    dnc2(2,n-1,1,n);
    cout<<ans;
    return 0;
}

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