oj.uz

Submission #515546

# Submission time Handle Problem Language Result Execution time Memory
515546 2022-01-19T08:34:31 Z 79brue Triple Jump (JOI19_jumps) C++14
46 / 100
 4000 ms 139380 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
int arr[500002];
int DP[5002][5002];
int DPmax[5002][5002];
int sparse[500002][20];

void init(){
    for(int i=1; i<=n; i++) sparse[i][0] = arr[i];
    for(int d=1; d<20; d++){
        for(int i=1; i<=n; i++) sparse[i][d] = max(sparse[i][d-1], (i+(1<<(d-1))) > n ? 0 : sparse[i+(1<<(d-1))][d-1]);
    }
}

int query(int l, int r){
    int d = 31-__builtin_clz(r-l+1);
    return max(sparse[l][d], sparse[r-(1<<d)+1][d]);
}

void solveSmall(){
    for(int i=1; i<=n; i++){
        DPmax[i][i] = arr[i];
        for(int j=i+1; j<=n; j++){
            DPmax[i][j] = max(DPmax[i][j-1], arr[j]);
        }
    }
    for(int i=1; i<=n-2; i++) DP[i][i+2] = arr[i] + arr[i+1] + arr[i+2];
    for(int d=3; d<n; d++){
        for(int i=1; i+d<=n; i++){
            int j = i+d;
            DP[i][j] = max({DP[i][j-1], DP[i+1][j], arr[i] + arr[j] + DPmax[i+1][(i+j)/2]});
        }
    }

    scanf("%d", &q);
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", DP[l][r]);
    }
    exit(0);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);

    if(n <= 5000) solveSmall();

    init();

    scanf("%d", &q);
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);

        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        vector<pair<int, int> > vec;

        vec.push_back(make_pair(arr[r], r));
        vec.push_back(make_pair(arr[r-1], r-1));
        for(auto p: vec) pq.push(p);

        int ans = 0;
        for(int a=r-2; a>=l; a--){
            for(pair<int, int> p: vec){
                int b = p.second;
                if(b-a>1) ans = max(ans, arr[a] + arr[b] + query(a+1, (a+b)/2));
                if(b*2<=a+r) ans = max(ans, arr[a] + arr[b] + query(b*2-a, r));
            }

            pq.push(make_pair(arr[a], a));
            vec.push_back(make_pair(arr[a], a));

            if(pq.size() >= 20){
                vec.erase(find(vec.begin(), vec.end(), pq.top()));
                pq.pop();
            }
        }

        printf("%d\n", ans);
    }
}

Compilation message

jumps.cpp: In function 'void solveSmall()':
jumps.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:51:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
jumps.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 457 ms 139380 KB Output is correct
12 Correct 444 ms 139184 KB Output is correct
13 Correct 448 ms 139172 KB Output is correct
14 Correct 455 ms 139196 KB Output is correct
15 Correct 466 ms 139140 KB Output is correct
16 Correct 452 ms 138592 KB Output is correct
17 Correct 453 ms 138480 KB Output is correct
18 Correct 466 ms 138504 KB Output is correct
19 Correct 446 ms 139052 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 16720 KB Output is correct
2 Correct 83 ms 16704 KB Output is correct
3 Correct 101 ms 16724 KB Output is correct
4 Correct 86 ms 16760 KB Output is correct
5 Correct 85 ms 16632 KB Output is correct
6 Correct 89 ms 16720 KB Output is correct
7 Correct 94 ms 16628 KB Output is correct
8 Correct 86 ms 16712 KB Output is correct
9 Correct 94 ms 16760 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 457 ms 139380 KB Output is correct
12 Correct 444 ms 139184 KB Output is correct
13 Correct 448 ms 139172 KB Output is correct
14 Correct 455 ms 139196 KB Output is correct
15 Correct 466 ms 139140 KB Output is correct
16 Correct 452 ms 138592 KB Output is correct
17 Correct 453 ms 138480 KB Output is correct
18 Correct 466 ms 138504 KB Output is correct
19 Correct 446 ms 139052 KB Output is correct
20 Correct 106 ms 16720 KB Output is correct
21 Correct 83 ms 16704 KB Output is correct
22 Correct 101 ms 16724 KB Output is correct
23 Correct 86 ms 16760 KB Output is correct
24 Correct 85 ms 16632 KB Output is correct
25 Correct 89 ms 16720 KB Output is correct
26 Correct 94 ms 16628 KB Output is correct
27 Correct 86 ms 16712 KB Output is correct
28 Correct 94 ms 16760 KB Output is correct
29 Execution timed out 4051 ms 41376 KB Time limit exceeded
30 Halted 0 ms 0 KB -