oj.uz

Submission #515545

# Submission time Handle Problem Language Result Execution time Memory
515545 2022-01-19T08:33:41 Z 79brue Triple Jump (JOI19_jumps) C++14
46 / 100
 4000 ms 139448 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() >= 100){
                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 460 ms 139276 KB Output is correct
12 Correct 455 ms 139388 KB Output is correct
13 Correct 461 ms 139448 KB Output is correct
14 Correct 451 ms 139424 KB Output is correct
15 Correct 448 ms 139384 KB Output is correct
16 Correct 456 ms 138788 KB Output is correct
17 Correct 483 ms 138820 KB Output is correct
18 Correct 466 ms 138768 KB Output is correct
19 Correct 467 ms 139356 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 16720 KB Output is correct
2 Correct 174 ms 16716 KB Output is correct
3 Correct 260 ms 16716 KB Output is correct
4 Correct 337 ms 16724 KB Output is correct
5 Correct 285 ms 16720 KB Output is correct
6 Correct 213 ms 16724 KB Output is correct
7 Correct 241 ms 16628 KB Output is correct
8 Correct 253 ms 16728 KB Output is correct
9 Correct 301 ms 16708 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 460 ms 139276 KB Output is correct
12 Correct 455 ms 139388 KB Output is correct
13 Correct 461 ms 139448 KB Output is correct
14 Correct 451 ms 139424 KB Output is correct
15 Correct 448 ms 139384 KB Output is correct
16 Correct 456 ms 138788 KB Output is correct
17 Correct 483 ms 138820 KB Output is correct
18 Correct 466 ms 138768 KB Output is correct
19 Correct 467 ms 139356 KB Output is correct
20 Correct 361 ms 16720 KB Output is correct
21 Correct 174 ms 16716 KB Output is correct
22 Correct 260 ms 16716 KB Output is correct
23 Correct 337 ms 16724 KB Output is correct
24 Correct 285 ms 16720 KB Output is correct
25 Correct 213 ms 16724 KB Output is correct
26 Correct 241 ms 16628 KB Output is correct
27 Correct 253 ms 16728 KB Output is correct
28 Correct 301 ms 16708 KB Output is correct
29 Execution timed out 4088 ms 42004 KB Time limit exceeded
30 Halted 0 ms 0 KB -