oj.uz

Submission #944994

# Submission time Handle Problem Language Result Execution time Memory
944994 2024-03-13T09:41:31 Z itslq Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 19932 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> A;

struct node {
    int l, r, m, v;
    node *lc, *rc;

    node(int _l, int _r): l(_l), r(_r) {
        m = (l + r) >> 1;
        if (l == r) {
            v = A[l];
        } else {
            lc = new node(l, m);
            rc = new node(m + 1, r);

            v = max(lc -> v, rc -> v);
        }
    }

    int query(int _l, int _r) {
        if (l == _l && r == _r) {
            return v;
        } else if (_r <= m) {
            return lc -> query(_l, _r);
        } else if (_l > m) {
            return rc -> query(_l, _r);
        } else {
            return max(lc -> query(_l, m), rc -> query(m + 1, _r));
        }
    }
} *root;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, Q, L, R, S;
    cin >> N;

    A.resize(N + 5);
    for (int i = 1; i <= N; i++) cin >> A[i];

    root = new node(1, N);

    cin >> Q;
    while (Q--) {
        S = 0;
        cin >> L >> R;
        for (int l = L; l + 2 <= R; l++) {
            for (int r = l + 2; r <= R; r++) {
                S = max(S, A[l] + A[r] + root -> query(l + 1, (l + r) >> 1));
            }
        }
        cout << S << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Execution timed out 4009 ms 856 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4037 ms 19932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Execution timed out 4009 ms 856 KB Time limit exceeded
12 Halted 0 ms 0 KB -