oj.uz

Submission #220783

# Submission time Handle Problem Language Result Execution time Memory
220783 2020-04-08T19:25:04 Z Toirov_Sadi Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 71240 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));
        }
    }
    cin >> q;
    while(q --){
        int l, r;
        int mx = 0;
        cin >> l >> r;
        assert(r - l + 1 >= 3);
        for(int i = 0; i <= n; i ++){
            if(l + i > n || r - l - i <= 1){
                break;
            }
            mx = max(mx, ans[l + i][r - l - i]);
        }
        cout << mx << "\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 892 KB Output is correct
10 Correct 5 ms 768 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 892 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Execution timed out 4073 ms 71240 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 1536 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 5 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 892 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Execution timed out 4073 ms 71240 KB Time limit exceeded
12 Halted 0 ms 0 KB -