Submission #1345349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345349		killerzaluu	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4065 ms	12948 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> h;
vector<int> ord;

void init(int N, vector<int> H) {
    n = N;
    h = H;
    ord.resize(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return h[a] > h[b];
    });
}

int minimum_jumps(int A, int B, int C, int D) {
    const int INF = 1e9;
    vector<int> dp(n, INF);
    set<int> s;

    for (int id : ord) {
        auto it = s.lower_bound(id);

        int best = INF;

        if (C <= id && id <= D) best = 0;

        if (it != s.end()) best = min(best, dp[*it] + 1);
        if (it != s.begin()) {
            --it;
            best = min(best, dp[*it] + 1);
        }

        dp[id] = best;
        s.insert(id);
    }

    int ans = INF;
    for (int i = A; i <= B; i++) ans = min(ans, dp[i]);

    if (ans == INF) return -1;
    return ans;
}

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19