| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 723447 | grossly_overconfident | Rainforest Jumps (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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){
if (a <= d && b <= c){
return 0;
}
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;
for (auto& e : dp){
for (auto f : e){
cout << f << " ";
}
cout << endl;
}
}
return 0;
}
*/