Submission #336394

#	Time	Username	Problem	Language	Result	Execution time	Memory
336394		KoD	Triple Jump (JOI19_jumps)	C++17	46 / 100	416 ms	104684 KiB

jumps

#include <bits/stdc++.h>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

template <class T>
using Vec = std::vector<T>;

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    usize N;
    std::cin >> N;
    Vec<u32> A(N);
    for (auto &x: A) {
        std::cin >> x;
    }
    usize Q;
    std::cin >> Q;
    if (Q <= 20) {
        while (Q--) {
            usize L, R;
            std::cin >> L >> R;
            L -= 1;
            R -= 1;
            std::stack<std::pair<u32, usize>> stack;
            Vec<u32> accum(N);
            accum[R] = A[R];
            for (usize i = R; i --> L;) {
                accum[i] = std::max(A[i], accum[i + 1]);
            }
            u32 ans = 0;
            for (usize m = L; m < R; ++m) {
                while (!stack.empty()) {
                    const auto [v, i] = stack.top();
                    if (m + m - i <= R) {
                        ans = std::max(ans, v + A[m] + accum[m + m - i]);
                    }
                    if (v > A[m]) {
                        break;
                    }
                    stack.pop();
                }
                stack.emplace(A[m], m);
            }
            std::cout << ans << '\n';
        }
    }
    else if (N <= 5000) {
        Vec<Vec<u32>> dp(N, Vec<u32>(N, 0));
        for (usize l = 0; l < N; ++l) {
            u32 m = 0;
            for (usize r = l + 2; r < N; ++r) {
                m = std::max(m, A[(l + r) / 2]);
                dp[l][r] = A[l] + m + A[r];
            }
        }
        for (usize len = 2; len < N; ++len) {
            for (usize l = 0; l + len < N; ++l) {
                dp[l][l + len] = std::max({ dp[l][l + len], dp[l + 1][l + len], dp[l][l + len - 1] }); 
            }
        }
        while (Q--) {
            usize l, r;
            std::cin >> l >> r;
            l -= 1;
            r -= 1;
            std::cout << dp[l][r] << '\n';
        }
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54