oj.uz

Submission #439040

# Submission time Handle Problem Language Result Execution time Memory
439040 2021-06-29T06:12:08 Z aris12345678 Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 23484 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 205;
bool sub1 = false;
vector<int> height;
int precomp[mxN][mxN];

int bfs(int i, int end) {
    int n = int(height.size());
    queue<pair<int, int> > q;
    q.push({i, 0});
    while(!q.empty()) {
        int u = q.front().first, jumps = q.front().second;
        q.pop();
        if(u == end)
            return jumps;
        if(height[u] > height[end]) continue;
        int j = u;
        while(j >= 0 && height[j] <= height[u])
            j--;
        // cout << "bfs_1: " << u << " " << j << " " << jumps+1 << "\n";
        if(j >= 0)
            q.push({j, jumps+1});
        j = u;
        while(j < n && height[j] <= height[u])
            j++;
        // cout << "bfs_2: " << u << " " << j << " " << jumps+1 << "\n";
        if(j < n)
            q.push({j, jumps+1});
    }
    return -1;
}

void init(int n, vector<int> h) {
    if(is_sorted(h.begin(), h.end()))
        sub1 = true;
    height = h;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)
            precomp[i][j] = INT_MAX;
    }
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            if(height[j] < height[i]) continue;
            int jumps = bfs(i, j);
            if(jumps != -1)
                precomp[i][j] = min(precomp[i][j], jumps);
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    if(sub1)
        return c-b;
    else {
        int ans = INT_MAX;
        for(int i = a; i <= b; i++) {
            for(int j = c; j <= d; j++)
                ans = min(ans, precomp[i][j]);
        }
        if(ans == INT_MAX)
            return -1;
        return ans;
    }
}

/*
int main() {
    int n = 7;
    vector<int> h = {3, 2, 1, 6, 4, 5, 7};
    init(n, h);
    int a = 0, b = 1, c = 2, d = 2;
    printf("%d\n", minimum_jumps(a, b, c, d));
    return 0;
}
*/

/*
0 1 2 3 4 5 6
3 2 1 6 4 5 7

(1, 3)
(5, 6)
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Runtime error 32 ms 4504 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Correct 4 ms 456 KB Output is correct
7 Correct 4 ms 328 KB Output is correct
8 Correct 5 ms 456 KB Output is correct
9 Correct 4 ms 328 KB Output is correct
10 Correct 9 ms 456 KB Output is correct
11 Correct 115 ms 328 KB Output is correct
12 Correct 111 ms 456 KB Output is correct
13 Correct 42 ms 328 KB Output is correct
14 Correct 8 ms 456 KB Output is correct
15 Execution timed out 4051 ms 23484 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Correct 4 ms 456 KB Output is correct
7 Correct 4 ms 328 KB Output is correct
8 Correct 5 ms 456 KB Output is correct
9 Correct 4 ms 328 KB Output is correct
10 Correct 9 ms 456 KB Output is correct
11 Correct 115 ms 328 KB Output is correct
12 Correct 111 ms 456 KB Output is correct
13 Correct 42 ms 328 KB Output is correct
14 Correct 8 ms 456 KB Output is correct
15 Execution timed out 4051 ms 23484 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 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 Runtime error 26 ms 4624 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Runtime error 20 ms 2888 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Runtime error 20 ms 2888 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Runtime error 32 ms 4504 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -