#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;
};
struct state {
bool friend operator<(const state& s1, const state& s2)
{
return s1.dist > s2.dist;
}
int p, s;
ll dist;
};
int hashState (int x, int y)
{
return (n + 1) * x + y;
}
struct edge {
int to; ll cost;
};
seg s[5005];
vector<vector<edge>> adj;
ll dist[5005][5005];
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 ()
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
dist[i][j] = 1e18;
}
}
priority_queue<state> q;
q.push({1, n-1, 0});
dist[1][n-1] = 0;
ll ans = -1;
while (!q.empty())
{
state crt = q.top();
// cout << crt.p << ' ' << crt.s << '\n';
// cout << crt.dist << '\n';
// int a; cin >> a;
q.pop();
if (crt.s >= n) continue;
if (crt.p == crt.s || crt.p == crt.s + 1)
{
ans = crt.dist;
break;
}
if (crt.dist > dist[crt.p][crt.s]) 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;
}
}*/
int i = crt.p, j = crt.s;
if (s[j].hmin > h[i] || s[j].hmax < h[i]) continue;
// cout << i << ' ' << j << ":\n";
if (i < n && 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 (dist[i+1][j] > dist[i][j] + abs(h[i] - h[i+1]))
{
dist[i+1][j] = dist[i][j] + abs(h[i] - h[i+1]);
q.push({i + 1, j, dist[i+1][j]});
}
}
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 (dist[i-1][j] > dist[i][j] + abs(h[i] - h[i-1]))
{
dist[i-1][j] = dist[i][j] + abs(h[i] - h[i-1]);
q.push({i - 1, j, dist[i-1][j]});
}
}
if (i < n && 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 (dist[j][i] > dist[i][j] + abs(h[j] - h[i]))
{
dist[j][i] = dist[i][j] + abs(h[j] - h[i]);
q.push({j, i, dist[j][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 (dist[j][i-1] > dist[i][j] + abs(h[j] - h[i]))
{
dist[j][i-1] = dist[i][j] + abs(h[j] - h[i]);
q.push({j, i-1, dist[j][i-1]});
}
}
if (i < n && j < n &&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 (dist[j+1][i] > dist[i][j] + abs(h[j+1] - h[i]))
{
dist[j+1][i] = dist[i][j] + abs(h[j+1] - h[i]);
q.push({j+1, i, dist[j+1][i]});
}
}
if (j < n && 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])});
if (dist[j+1][i-1] > dist[i][j] + abs(h[j+1] - h[i]))
{
dist[j+1][i-1] = dist[i][j] + abs(h[j+1] - h[i]);
q.push({j+1, i-1, dist[j+1][i]});
}
}
}
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';
}
Compilation message
climbers.cpp:245:3: warning: "/*" within comment [-Wcomment]
245 | /* for (int i = 1; i <= (n + 1) * n; i++)
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
2132 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
12112 KB |
Output isn't correct |
| 4 |
Incorrect |
43 ms |
82704 KB |
Output isn't correct |
| 5 |
Incorrect |
87 ms |
196268 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
3028 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
728 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2004 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
11404 KB |
Output isn't correct |
| 4 |
Incorrect |
33 ms |
76120 KB |
Output isn't correct |
| 5 |
Incorrect |
39 ms |
75448 KB |
Output isn't correct |
| 6 |
Incorrect |
59 ms |
137828 KB |
Output isn't correct |
| 7 |
Incorrect |
61 ms |
130268 KB |
Output isn't correct |
| 8 |
Incorrect |
100 ms |
186080 KB |
Output isn't correct |
| 9 |
Incorrect |
81 ms |
187848 KB |
Output isn't correct |
| 10 |
Incorrect |
84 ms |
185724 KB |
Output isn't correct |
