oj.uz

Submission #146066

# Submission time Handle Problem Language Result Execution time Memory
146066 2019-08-21T19:02:22 Z fedoseevtimofey Triple Jump (JOI19_jumps) C++14
27 / 100
 43 ms 5708 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector <int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    vector <int> sufMax(n);
    for (int i = n - 1; i >= 0; --i) {
        sufMax[i] = A[i];
        if (i + 1 < n) sufMax[i] = max(sufMax[i], sufMax[i + 1]);
    }
    vector <int> L(n, -1), R(n, n);
    vector <pair <int, int>> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && st.back().first < A[i]) st.pop_back();
        if (!st.empty()) L[i] = st.back().second;
        st.push_back({A[i], i});
    }
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && st.back().first <= A[i]) st.pop_back();
        if (!st.empty()) R[i] = st.back().second;
        st.push_back({A[i], i});
    }
    int ans = 0;
    auto check = [&] (int i, int j) {
        int minK = j + j - i;
        if (minK < n) {
            ans = max(ans, A[i] + A[j] + sufMax[minK]);
        }
    };
    for (int i = 0; i < n; ++i) {
        int j = L[i];
        if (j != -1) check(j, i);
        j = R[i];
        if (j != n) check(i, j);
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << ans << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3480 KB Output is correct
2 Correct 38 ms 5644 KB Output is correct
3 Correct 41 ms 5708 KB Output is correct
4 Correct 42 ms 3448 KB Output is correct
5 Correct 43 ms 5368 KB Output is correct
6 Correct 36 ms 4600 KB Output is correct
7 Correct 36 ms 4484 KB Output is correct
8 Correct 35 ms 4472 KB Output is correct
9 Correct 39 ms 4856 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -