oj.uz

Submission #336333

# Submission time Handle Problem Language Result Execution time Memory
336333 2020-12-15T05:01:07 Z KoD Triple Jump (JOI19_jumps) C++14
19 / 100
 1747 ms 108452 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1691 ms 108268 KB Output is correct
12 Correct 1747 ms 108228 KB Output is correct
13 Correct 1696 ms 108420 KB Output is correct
14 Correct 1677 ms 108452 KB Output is correct
15 Correct 1702 ms 108248 KB Output is correct
16 Correct 1714 ms 107628 KB Output is correct
17 Correct 1675 ms 107628 KB Output is correct
18 Correct 1675 ms 107596 KB Output is correct
19 Correct 1687 ms 108144 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 2924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1691 ms 108268 KB Output is correct
12 Correct 1747 ms 108228 KB Output is correct
13 Correct 1696 ms 108420 KB Output is correct
14 Correct 1677 ms 108452 KB Output is correct
15 Correct 1702 ms 108248 KB Output is correct
16 Correct 1714 ms 107628 KB Output is correct
17 Correct 1675 ms 107628 KB Output is correct
18 Correct 1675 ms 107596 KB Output is correct
19 Correct 1687 ms 108144 KB Output is correct
20 Incorrect 83 ms 2924 KB Output isn't correct
21 Halted 0 ms 0 KB -