제출 #723461

#제출 시각아이디문제언어결과실행 시간메모리
723461grossly_overconfident밀림 점프 (APIO21_jumps)C++17
21 / 100
1227 ms1048576 KiB
#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, -2)); 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; break; } } } } int solve(int s, int f){ if (s == f){ return 0; } if (dp[s][f] != -2){ 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 (auto l : adj){ cout << l.first << " " << l.second << endl; } 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; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...