oj.uz

Submission #242308

# Submission time Handle Problem Language Result Execution time Memory
242308 2020-06-27T08:39:12 Z tqbfjotld Triple Jump (JOI19_jumps) C++14
0 / 100
 4000 ms 37292 KB 
#include <bits/stdc++.h>
using namespace std;

long long arr[500005];
long long memo[5005][5005];

struct node{
    int s,e;
    long long v;
    node *l,*r;
    node(int _s, int _e){
    s = _s;
    e = _e;
    if (s==e) v = arr[s];
    else{
        l = new node(s,(s+e)/2);
        r = new node((s+e)/2+1,e);
        v = max(l->v,r->v);
    }
    }
    long long qu(int a, int b){
        if (b<a) return -99999999999999LL;
        if (a<=s && e<=b) return v;
        if (a<=(s+e)/2) return l->qu(a,b);
        if (b>(s+e)/2) return r->qu(a,b);
        return max(l->qu(a,b),r->qu(a,b));
    }
}*root;

int main(){
    int n,q;
    scanf("%d",&n);
    for (int x = 0; x<n; x++){
        scanf("%lld",&arr[x]);
    }
    scanf("%d",&q);
    if (false){
        for (int x = 0; x<q; x++){
            int l,r;
            scanf("%d%d",&l,&r);
            l--;r--;
            long long ans = 0;
            for (int a = l; a<=r; a++){
                for (int c = a+2; c<=r; c++){
                    for (int b = a+1; c-b>=b-a; b++){
                        ans = max(ans,arr[a]+arr[b]+arr[c]);
                    }
                }
            }
            printf("%lld\n",ans);
        }
    }
    else{
        root = new node(0,n);
        for (int x = 0; x<n; x++){
            for (int y = 0; y<n; y++){
                memo[x][y] = root->qu(x+1,(x+y)/2) + arr[x]+arr[y];
            }
        }
        for (int x = 0; x<n; x++){
            for (int y = 1; y<n; y++){
                memo[x][y] = max(memo[x][y],memo[x][y-1]);
            }
        }
        for (int x = n-2; x>=0; x--){
            for (int y = 0; y<n; y++){
                memo[x][y] = max(memo[x][y],memo[x+1][y]);
            }
        }
        for (int x = 0; x<q; x++){
            int l,r;
            scanf("%d%d",&l,&r);
            l--;r--;
            printf("%lld\n",memo[l][r]);
        }
    }
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~
jumps.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 896 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 4061 ms 37292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -