oj.uz

Submission #944059

# Submission time Handle Problem Language Result Execution time Memory
944059 2024-03-12T07:53:00 Z beepbeepsheep Triple Jump (JOI19_jumps) C++17
0 / 100
 730 ms 27276 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 27276 KB Output is correct
2 Correct 410 ms 27048 KB Output is correct
3 Correct 659 ms 27220 KB Output is correct
4 Correct 717 ms 27048 KB Output is correct
5 Correct 711 ms 27052 KB Output is correct
6 Correct 730 ms 26960 KB Output is correct
7 Incorrect 720 ms 27048 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -