oj.uz

Submission #723454

# Submission time Handle Problem Language Result Execution time Memory
723454 2023-04-13T20:17:49 Z grossly_overconfident Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 697 ms 1048576 KB 
//#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
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 = -1;
    for (int i = a; i <= b; ++i){
        for (int j = c; j <= d; ++j){
            int s = solve(i, j);
            if (s != -1){
                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;
        for (auto& e : dp){
            for (auto f : e){
                cout << f << " ";
            }
            cout << endl;
        }
    }


    return 0;
}
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 697 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Incorrect 43 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Incorrect 43 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Runtime error 383 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Runtime error 510 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Runtime error 510 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 697 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -