Submission #722467

#	Time	Username	Problem	Language	Result	Execution time	Memory
722467		grossly_overconfident	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 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; j < n; ++j){
            if (h[j] > h[i]){
                adj[i].second = j;
                break;
            }
        }
        for (int j = i; j >= 0; --j){
            if (h[j] > h[i]){
                adj[i].first = j;
            }
        }
    }
}

int solve(int s, int f){
    if (s == f){
        return 0;
    }
    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;
}
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/cc3uuErI.o: in function `main':
stub.cpp:(.text.startup+0x177): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: stub.cpp:(.text.startup+0x1d1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status