제출 #442319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442319		maksim1744	밀림 점프 (APIO21_jumps)	C++17	0 / 100	4059 ms	4508 KiB

jumps

/*
    author:  Maksim1744
    created: 07.07.2021 15:38:41
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "C:/C++ libs/print.cpp"
#else
#define show(...) void(0)
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#endif

const int inf = 1e9;

int n;
vector<int> h;
vector<int> to;
void init(int n_, vector<int> h_) {
    n = n_;
    h = h_;
    vector<int> st;
    to.assign(n, n);
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && h[st.back()] <= h[i])
            st.pop_back();
        if (!st.empty())
            to[i] = st.back();
        st.pb(i);
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    vector<int> dp(n, inf);
    for (int i = a; i <= b; ++i)
        dp[i] = 0;
    for (int i = 0; i < n; ++i)
        if (to[i] < n)
            dp[to[i]] = min(dp[to[i]], dp[i] + 1);

    int ans = inf;
    for (int i = c; i <= d; ++i)
        ans = min(ans, dp[i]);
    if (ans == inf) ans = -1;
    return ans;
}

#ifdef HOUSE
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    

    return 0;
}
#endif

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