Submission #723435

#	Time	Username	Problem	Language	Result	Execution time	Memory
723435		grossly_overconfident	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	549 ms	1048576 KiB

jumps

//#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
vector<vector<int>> dp;
vector<pair<int, int>> adj;
vector<int> h;

void init(int n, vector<int> H){
    vector<vector<int>> build(n + 10, vector<int>(n + 10, -1));
    dp = build;
    h = H;
    adj.resize(n);
    for (int i = 0; i < n; ++i){
        adj[i] = {-1, -1};
        for (int j = i + 1; j < n; ++j){
            if (h[j] > h[i]){
                adj[i].second = j;
                break;
            }
        }
        for (int j = i - 1; j >= 0; --j){
            if (h[j] > h[i]){
                adj[i].first = j;
            }
        }
    }
}

int solve(int s, int f){
    if (s == f){
        return 0;
    }
    if (dp[s][f] != -1){
        return dp[s][f];
    }
    int op1 = -1, op2 = -1;
    if (adj[s].first != -1){
        op1 = solve(adj[s].first, f);
        if (op1 != -1){
            op1++;
        }
    }
    if (adj[s].second != -1){
        op2 = solve(adj[s].second, f);
        if (op2 != -1){
            op2++;
        }
    }
    if (op1 + op2 == -2){
        return dp[s][f] = -1;
    }
    if (op1 == -1){
        return dp[s][f] = op2;
    }
    if (op2 == -1){
        return dp[s][f] = op1;
    }
    return dp[s][f] = min(op1, op2);
}

int minimum_jumps(int a, int b, int c, int d){
    int best = INT_MAX;
    for (int i = a; i <= b; ++i){
        for (int j = c; j <= d; ++j){
            if (best == -1){
                best = solve(i, j);
            }
            else{
                best = min(best, solve(i, j));
            }
        }
    }
    return best;
}
/*
signed main(){
    
    //cin.tie(0);
    //iostream::sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector<int> k(n);
    for (int i = 0; i < n; ++i){
        cin >> k[i];
    }
    init(n, k);
    for (int i = 0; i < q; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << endl;
    }


    return 0;
}
*/

• 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