Submission #641314

#TimeUsernameProblemLanguageResultExecution timeMemory
641314RaulAndrei01Climbers (RMI18_climbers)C++17
55 / 100
893 ms524288 KiB
#include <bits/stdc++.h> #include <vector> #include <queue> using namespace std; typedef long long ll; ll h[5005]; int n; bool check(int i) { if (h[i-2] <= h[i-1] && h[i-1] <= h[i]) return 1; if (h[i-2] >= h[i-1] && h[i-1] >= h[i]) return 1; return 0; } struct seg { ll hmax, hmin; bool dir; }; int hashState (int x, int y) { return (n + 1) * x + y; } struct edge { int to; ll cost; }; seg s[5005]; vector<vector<edge>> adj; vector<ll> dist; bool unhash (int x) { int f = x % (n + 1); int s = x / (n + 1); if (f == s) return 1; if (s == f + 1) return 1; return 0; } ll dijsktra () { priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; q.push({0, hashState(1, n-1)}); dist[hashState(1, n - 1)] = 0; ll ans = -1; while (!q.empty()) { pair<ll, int> crt = q.top(); q.pop(); // cout << crt.first << '\n'; // cout << crt.second / (n + 1) << ' ' << crt.second % (n + 1) << '\n'; if (unhash(crt.second)) { ans = crt.first; break; } if (crt.first > dist[crt.second]) continue; for (auto to : adj[crt.second]) { // cout << dist[to.to] << ' '; if (dist[to.to] > dist[crt.second] + to.cost) { q.push({dist[crt.second] + to.cost, to.to}); dist[to.to] = dist[crt.second] + to.cost; } } } return ans; } int main () { cin >> n; for (int i = 1; i <= n; i++) { cin >> h[i]; if (i > 2 && check(i)) { n--; i--; h[i] = h[i+1]; h[i+1] = 0; } } dist.resize((n + 2) * (n + 1) + 2, 1e18); adj.resize((n + 2) * (n + 1) + 3); for (int i = 1; i < n; i++) { s[i] = {max(h[i], h[i+1]), min(h[i], h[i+1])}; if (h[i] < h[i+1]) s[i].dir = 1; // cout << s[i].hmin << ' ' << s[i].hmax << '\n'; } for (int i = 1; i <= n; i++) { for (int j = 1; j < n; j++) { if (s[j].hmin > h[i] || s[j].hmax < h[i]) continue; // cout << i << ' ' << j << ":\n"; if (h[i+1] >= s[j].hmin && h[i+1] <= s[j].hmax) { // cout << h[i+1] << ' ' << s[j].hmin << ' ' << s[j].hmax << '\n'; // cout << hashState(i, j) << ' ' << hashState(i + 1, j) << '\n'; adj[hashState(i, j)].push_back({hashState(i + 1, j), abs(h[i] - h[i+1])}); adj[hashState(i + 1, j)].push_back({hashState(i, j), abs(h[i] - h[i+1])}); } if (i > 1 && h[i-1] >= s[j].hmin && h[i-1] <= s[j].hmax) { // cout << h[i-1] << ' ' << s[j].hmin << ' ' << s[j].hmax << '\n'; // cout << hashState(i, j) << ' ' << hashState(i - 1, j) << '\n'; adj[hashState(i, j)].push_back({hashState(i - 1, j), abs(h[i] - h[i-1])}); adj[hashState(i - 1, j)].push_back({hashState(i, j), abs(h[i] - h[i-1])}); } if (h[j] >= s[i].hmin && h[j] <= s[i].hmax) { // cout << h[j] << ' ' << s[i].hmin << ' ' << s[i].hmax << '\n'; // cout << hashState(i, j) << ' ' << hashState(j, i) << '\n'; adj[hashState(i, j)].push_back({hashState(j, i), abs(h[j] - h[i])}); adj[hashState(j, i)].push_back({hashState(i, j), abs(h[j] - h[i])}); } if (i > 1 && h[j] >= s[i-1].hmin && h[j] <= s[i-1].hmax) { // cout << h[j] << ' ' << s[i-1].hmin << ' ' << s[i-1].hmax << '\n'; // cout << hashState(i, j) << ' ' << hashState(j, i-1) << '\n'; adj[hashState(i, j)].push_back({hashState(j, i-1), abs(h[j] - h[i])}); adj[hashState(j, i-1)].push_back({hashState(i, j), abs(h[j] - h[i])}); } if (h[j+1] >= s[i].hmin && h[j+1] <= s[i].hmax) { // cout << h[j+1] << ' ' << s[i].hmin << ' ' << s[i].hmax << '\n'; // cout << hashState(i, j) << ' ' << hashState(j+1, i) << '\n'; adj[hashState(i, j)].push_back({hashState(j+1, i), abs(h[j+1] - h[i])}); adj[hashState(j+1, i)].push_back({hashState(i, j), abs(h[j+1] - h[i])}); } if (i > 1 && h[j+1] >= s[i-1].hmin && h[j+1] <= s[i-1].hmax) { // cout << h[j+1] << ' ' << s[i-1].hmin << ' ' << s[i-1].hmax << '\n'; // cout << hashState(i, j) << ' ' << hashState(j+1, i-1) << '\n'; adj[hashState(i, j)].push_back({hashState(j+1, i-1), abs(h[j+1] - h[i])}); adj[hashState(j+1, i-1)].push_back({hashState(i, j), abs(h[j+1] - h[i])}); } } } /* for (int i = 1; i <= (n + 1) * n; i++) { cout << i / (n + 1) << ' ' << i % (n + 1) << ":\n"; for (auto to : adj[i]) cout << " " << to.to / (n + 1) << ' ' << to.to % (n + 1) << ' ' << to.cost << '\n'; }*/ cout << dijsktra() << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...