oj.uz

Submission #1096681

# Submission time Handle Problem Language Result Execution time Memory
1096681 2024-10-05T02:19:36 Z nguyenvu Triple Jump (JOI19_jumps) C++14
5 / 100
 4000 ms 7768 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Execution timed out 4035 ms 600 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4019 ms 7768 KB Time limit exceeded
2 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 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Execution timed out 4035 ms 600 KB Time limit exceeded
12 Halted 0 ms 0 KB -