oj.uz

Submission #793281

# Submission time Handle Problem Language Result Execution time Memory
793281 2023-07-25T17:14:55 Z anton Triple Jump (JOI19_jumps) C++17
0 / 100
 4000 ms 8164 KB 
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define int long long

const int MAX_N = 5*1e5;
const int INF = 1e9;
const int K = 2*1e2;
int n, q;
pii A[MAX_N];
pii B[K];
int lower_sum = 0;
int tree[MAX_N*4];

void build(int lt, int rt, int t){
    if(lt == rt){
        tree[t] = A[lt].first;
    }
    else{
        int mid = (lt+rt)/2;
        build(lt, mid, t*2);
        build(mid+1, rt, t*2+1);
        tree[t] = max(tree[t*2], tree[t*2+1]);
    }
}

int get(int l, int r, int lt, int rt, int t){
    if(l<=lt && rt<= r){
        return tree[t];
    }
    else if(rt<l || r<lt){
        return -INF;
    }
    else{
        int mid = (lt+rt)/2;

        return max(get(l, r, lt, mid, t*2), get(l, r, mid+1, rt, t*2+1));
    }
}

int get(int l, int r){
    l = max(l, 0LL);
    r= min(r, n-1);
    //cout<<"get "<<l<<" "<<r<<endl;
    if(l>r){
        return -INF;
    }
    return get(l, r, 0, n-1, 1);
}

int get_score(int a, int b){

    //cout<<a<<" "<<b<<endl;
    if(a==b){
        return -INF;
    }
    if(a>b){
        return get_score(b, a);
    }
    int s=  A[a].first + A[b].first;
    int other = 0;
    int d= b-a;
    other = max(other, get(0, a-d));
    other = max(other, get(a+1, a+(d/2)));
    other = max(other, get(b+d, n-1));
    return s+other;
}

signed main(){
    cin>>n;

    for(int i = 0; i<n; i++){
        cin>>A[i].first;
        A[i].second = i;
    }

    auto cmp1 =[&](pii a, pii b){return a.first>b.first;};
    sort(A, A +n, cmp1);
    int s= min(n, K);
    for(int i = 0; i<s; i++){
        B[i] = A[i];
    }
    auto cmp2 = [&](pii a, pii b){return a.second<b.second;};
    sort(A, A+n, cmp2);


    cin>>q;
    for(int i = 0; i<q; i++){
        int a, b;
        cin>>a>>b;
    }

    build(0, n-1, 1);

    //cout<<lower_sum<<endl;

    int res= 0;

    for(int i = 0; i<n; i++){
        for(int j = 0; j<s; j++){
            res=max(res, get_score(i, B[j].second)); 
        }
    }
    cout<<res<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Incorrect 2 ms 304 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Incorrect 2 ms 304 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4032 ms 8164 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 360 KB Output is correct
2 Incorrect 2 ms 304 KB Output isn't correct
3 Halted 0 ms 0 KB -