Submission #336333

#	Time	Username	Problem	Language	Result	Execution time	Memory
336333		KoD	Triple Jump (JOI19_jumps)	C++14	19 / 100	1747 ms	108452 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() {
    usize N;
    std::cin >> N;
    std::vector<u32> A(N);
    for (auto &x: A) {
        std::cin >> x;
    }
    if (N <= 5000) {
        std::vector<std::vector<u32>> dp(N, std::vector<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] }); 
            }
        }
        usize Q;
        std::cin >> Q;
        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: 0 / 27
• Subtask 4: 0 / 54