# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
439022 | 2021-06-29T05:26:56 Z | aris12345678 | Rainforest Jumps (APIO21_jumps) | C++14 | 1168 ms | 2624 KB |
#include <bits/stdc++.h> using namespace std; const int mxN = 200005; bool sub1 = false; vector<int> height; void init(int n, vector<int> h) { if(is_sorted(h.begin(), h.end())) sub1 = true; height = h; return; } 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; int j = u; while(j >= 0 && height[j] <= height[u]) j--; if(j >= 0) q.push({j, jumps+1}); j = u; while(j < n && height[j] <= height[u]) j++; if(j < n) q.push({j, jumps+1}); } assert(true); } 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++) { int pos = i; for(int j = c; j <= d; j++) { if(height[j] < height[i]) continue; int jumps = bfs(pos, j); ans = min(ans, jumps); } } } } /* 3 2 1 6 4 5 7 (1, 3) (5, 6) */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 200 KB | Output is correct |
2 | Correct | 1 ms | 200 KB | Output is correct |
3 | Correct | 163 ms | 2144 KB | Output is correct |
4 | Correct | 1168 ms | 2568 KB | Output is correct |
5 | Correct | 853 ms | 1344 KB | Output is correct |
6 | Correct | 1088 ms | 2624 KB | Output is correct |
7 | Correct | 912 ms | 1812 KB | Output is correct |
8 | Correct | 1000 ms | 2624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 328 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 328 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 328 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 200 KB | Output is correct |
2 | Runtime error | 1 ms | 328 KB | Execution killed with signal 6 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 200 KB | Output is correct |
2 | Runtime error | 1 ms | 328 KB | Execution killed with signal 6 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 200 KB | Output is correct |
2 | Correct | 1 ms | 200 KB | Output is correct |
3 | Correct | 163 ms | 2144 KB | Output is correct |
4 | Correct | 1168 ms | 2568 KB | Output is correct |
5 | Correct | 853 ms | 1344 KB | Output is correct |
6 | Correct | 1088 ms | 2624 KB | Output is correct |
7 | Correct | 912 ms | 1812 KB | Output is correct |
8 | Correct | 1000 ms | 2624 KB | Output is correct |
9 | Runtime error | 1 ms | 328 KB | Execution killed with signal 6 |
10 | Halted | 0 ms | 0 KB | - |