oj.uz

답안 #442319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442319 2021-07-07T12:43:28 Z maksim1744 밀림 점프 (APIO21_jumps) C++17
0 / 100
 4000 ms 4508 KB 
/*
    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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Execution timed out 4059 ms 3832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Incorrect 3 ms 200 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Incorrect 3 ms 200 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 24 ms 2716 KB Output is correct
6 Correct 36 ms 3360 KB Output is correct
7 Correct 14 ms 1864 KB Output is correct
8 Correct 43 ms 3344 KB Output is correct
9 Correct 7 ms 840 KB Output is correct
10 Correct 33 ms 3368 KB Output is correct
11 Correct 31 ms 4508 KB Output is correct
12 Correct 30 ms 4492 KB Output is correct
13 Incorrect 30 ms 4488 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Execution timed out 4043 ms 1624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Execution timed out 4043 ms 1624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Execution timed out 4059 ms 3832 KB Time limit exceeded
4 Halted 0 ms 0 KB -