oj.uz

Submission #220784

# Submission time Handle Problem Language Result Execution time Memory
220784 2020-04-08T19:32:19 Z Toirov_Sadi Triple Jump (JOI19_jumps) C++17
19 / 100
 1489 ms 77560 KB 
#include <bits/stdc++.h>

#define FILE
#define fr first
#define se second

using namespace std;

const long long M = 21;
const long long N = 5e3 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int n;
int q;
int a[N];
int lg[N];
int d[N][M];
int ans[N][N];
int get(int l, int r){
    if(l > r){
        return 0;
    }
    int h = (r - l + 1);
    return max(d[l][lg[h]], d[r - (1 << lg[h]) + 1][lg[h]]);
}
int main()
{
    #ifdef FILEs
        freopen("input.txt", "r", stdin);
        /// freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);

    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        d[i][0] = a[i];
    }
    lg[2] = 1;
    for(int i = 3; i < N; i ++){
        lg[i] = lg[i / 2] + 1;
    }
    for(int j = 1; j < M; j ++){
        for(int i = 1; i + (1 << j) - 1 <= n; i ++){
            d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
        }
    }
    for(int l = 2; l < n; l ++){
        /// cout << "length: " << l << ":\n";
        for(int i = 1; i + l <= n; i ++){
            /// cout << "\t" << i << " (" << i + 1 << ", " << (2 * i + l) / 2 << ") " << i + l << "\n";
            /// cout << "\t" << a[i] << " " << get(i + 1, (2 * i + l) / 2) << " " << a[i + l] << "\n";
            ans[i][l] = max(ans[i][l - 1], a[i] + a[i + l] + get(i + 1, (2 * i + l)/ 2));
        }
    }
    for(int l = 2; l < n; l ++){
        for(int i = 1; i + l <= n; i ++){
            ans[i][l] = max(ans[i][l], ans[i + 1][l - 1]);
        }
    }
    cin >> q;
    while(q --){
        int l, r;
        int mx = 0;
        cin >> l >> r;
        assert(r - l + 1 >= 3);
        cout << ans[l][r - l] << "\n";
    }
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:66:13: warning: unused variable 'mx' [-Wunused-variable]
         int mx = 0;
             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 1453 ms 76152 KB Output is correct
12 Correct 1447 ms 77504 KB Output is correct
13 Correct 1458 ms 77560 KB Output is correct
14 Correct 1475 ms 77536 KB Output is correct
15 Correct 1469 ms 77432 KB Output is correct
16 Correct 1466 ms 76780 KB Output is correct
17 Correct 1454 ms 76920 KB Output is correct
18 Correct 1476 ms 76880 KB Output is correct
19 Correct 1489 ms 77376 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 1453 ms 76152 KB Output is correct
12 Correct 1447 ms 77504 KB Output is correct
13 Correct 1458 ms 77560 KB Output is correct
14 Correct 1475 ms 77536 KB Output is correct
15 Correct 1469 ms 77432 KB Output is correct
16 Correct 1466 ms 76780 KB Output is correct
17 Correct 1454 ms 76920 KB Output is correct
18 Correct 1476 ms 76880 KB Output is correct
19 Correct 1489 ms 77376 KB Output is correct
20 Runtime error 11 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -