oj.uz

Submission #431805

# Submission time Handle Problem Language Result Execution time Memory
431805 2021-06-17T15:41:26 Z ScarletS Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 3120 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int N = 5e5+7;
int a[N], s[N<<4];

void build(int i, int l, int r)
{
    if (l==r)
    {
        s[i]=a[l];
        return;
    }
    build(i*2+1,l,l+(r-l)/2);
    build(i*2+2,l+(r-l)/2+1,r);
    s[i]=max(s[i*2+1],s[i*2+2]);
}

int query(int i, int l, int r, int qL, int qR)
{
    assert(qL<=qR);
    if (qR<l||r<qL)
        return 0;
    if (qL<=l&&r<=qR)
        return s[i];
    return max(query(i*2+1,l,l+(r-l)/2,qL,qR),query(i*2+2,l+(r-l)/2+1,r,qL,qR));
}
  
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q,l,r,ans;
    cin>>n;
    for (int i=1;i<=n;++i)
        cin>>a[i];
    build(0,1,n);
    cin>>q;
    while (q--)
    {
        cin>>l>>r;
        ans=0;
        for (int i=l;i<=r;++i)
            for (int j=i+1;j*2-i<=r;++j)
                ans=max(ans,a[i]+a[j]+query(0,1,n,j*2-i,r));
        cout<<ans<<"\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 204 KB Output is correct
3 Correct 5 ms 204 KB Output is correct
4 Correct 5 ms 204 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 5 ms 204 KB Output is correct
7 Correct 5 ms 204 KB Output is correct
8 Correct 5 ms 324 KB Output is correct
9 Correct 6 ms 204 KB Output is correct
10 Correct 4 ms 332 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 204 KB Output is correct
3 Correct 5 ms 204 KB Output is correct
4 Correct 5 ms 204 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 5 ms 204 KB Output is correct
7 Correct 5 ms 204 KB Output is correct
8 Correct 5 ms 324 KB Output is correct
9 Correct 6 ms 204 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Execution timed out 4093 ms 332 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 4075 ms 3120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 204 KB Output is correct
3 Correct 5 ms 204 KB Output is correct
4 Correct 5 ms 204 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 5 ms 204 KB Output is correct
7 Correct 5 ms 204 KB Output is correct
8 Correct 5 ms 324 KB Output is correct
9 Correct 6 ms 204 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Execution timed out 4093 ms 332 KB Time limit exceeded
12 Halted 0 ms 0 KB -