#include <bits/stdc++.h>
#define all(x) ((x).begin(), (x).end())
#define sz(x) ((int) (x).size())
using namespace std;
typedef long long lint;
typedef pair<lint,lint> ii;
const lint inf = 12345678901234;
lint H[5005];
int n;
int to(int peak, int slope){
return peak * 6000 + slope;
}
lint dis[3100005];
vector<ii> adj[3100005];
void addEdge(int u, int v){
int pu = u / 6000;
int pv = v / 6000;
int su = u % 6000;
int sv = v % 6000;
//if(pv == 2 && sv == 3 && pu == 3 && su == 1) cout << "FDDF\n";
int w = abs(H[pu] - H[pv]);
adj[u].push_back(ii(w,v));
adj[v].push_back(ii(w,u));
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 0;i < n;i++) cin >> H[i];
if(n == 3){
cout << H[1];
return 0;
}
vector<int> v;
v.push_back(0);
for(int i = 1;i < n-1;i++){
if(H[i-1] > H[i] && H[i] > H[i+1]) continue;
if(H[i-1] < H[i] && H[i] < H[i+1]) continue;
v.push_back(H[i]);
}
v.push_back(0);
n = sz(v);
for(int i = 0;i < n;i++) H[i] = v[i];
for(int peak = 1;peak < n-1;peak++){
for(int slope = 0;slope < n-1;slope++){
int cur = to(peak,slope);
if(H[peak] > H[slope] && H[peak] > H[slope+1]) continue;
if(H[peak] < H[slope] && H[peak] < H[slope+1]) continue;
if(peak&1){ ///is peak
int slopeEnd;
if(slope & 1) slopeEnd = slope+1;
else slopeEnd = slope;
///go right
if(H[slopeEnd] >= H[peak+1]){
int nxt = to(slopeEnd, peak);
addEdge(cur,nxt);
}
else{
int nxt = to(peak+1, slope);
addEdge(cur,nxt);
}
///go left
if(H[slopeEnd] >= H[peak-1]){
int nxt = to(slopeEnd, peak-1);
addEdge(cur,nxt);
}
else{
int nxt = to(peak-1, slope);
addEdge(cur,nxt);
}
}
else{ ///is valley
int slopeEnd;
if(slope & 1) slopeEnd = slope;
else slopeEnd = slope + 1;
///go right
if(H[slopeEnd] <= H[peak+1]){
int nxt = to(slopeEnd, peak);
addEdge(cur,nxt);
}
else{
int nxt = to(peak+1, slope);
addEdge(cur,nxt);
}
///go left
if(H[slopeEnd] <= H[peak-1]){
//if(peak == 2 && slope == 3) cout << slopeEnd << "FFD\n";
int nxt = to(slopeEnd, peak-1);
addEdge(cur,nxt);
}
else{
//if(peak == 2 && slope == 3) cout << slopeEnd << "FFD\n";
int nxt = to(peak-1, slope);
addEdge(cur,nxt);
}
}
}
}
fill(dis,dis+3100005,inf);
int S = 0;
if(H[1] < H[n-2]){
S = to(1,n-2);
}
else S = to(n-2,0);
priority_queue<ii, vector<ii>, greater<ii> > pq;
dis[S] = 0; pq.push(ii(0,S));
while(!pq.empty()){
ii cur = pq.top(); pq.pop();
int peak = cur.second / 6000;
int slope = cur.second % 6000;
for(ii nei : adj[cur.second]){
if(dis[nei.second] > nei.first + cur.first){
int npeak = nei.second / 6000;
int nslope = nei.second % 6000;
//cout << peak << " " << slope << " " << cur.first << " " << npeak << " " << nslope << " " << nei.first << "\n";
dis[nei.second] = nei.first + cur.first;
pq.push(ii(dis[nei.second], nei.second));
}
}
}
lint ans = inf;
for(int peak = 1;peak < n-1;peak++){
int slope = peak;
//cout << peak << " " << slope << " " << dis[to(peak,slope)] << "P\n";
ans = min(ans, dis[to(peak,slope)]);
slope = peak-1;
//cout << peak << " " << slope << " " << dis[to(peak,slope)] << "P\n";
ans = min(ans, dis[to(peak,slope)]);
}
ans += min(H[1], H[n-2]);
cout << ans;
}
Compilation message
climbers.cpp: In function 'void addEdge(int, int)':
climbers.cpp:22:6: warning: unused variable 'su' [-Wunused-variable]
int su = u % 6000;
^~
climbers.cpp:23:6: warning: unused variable 'sv' [-Wunused-variable]
int sv = v % 6000;
^~
climbers.cpp: In function 'int main()':
climbers.cpp:149:9: warning: unused variable 'npeak' [-Wunused-variable]
int npeak = nei.second / 6000;
^~~~~
climbers.cpp:150:9: warning: unused variable 'nslope' [-Wunused-variable]
int nslope = nei.second % 6000;
^~~~~~
climbers.cpp:142:7: warning: unused variable 'peak' [-Wunused-variable]
int peak = cur.second / 6000;
^~~~
climbers.cpp:143:7: warning: unused variable 'slope' [-Wunused-variable]
int slope = cur.second % 6000;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
97784 KB |
Output is correct |
| 2 |
Correct |
70 ms |
100344 KB |
Output is correct |
| 3 |
Runtime error |
138 ms |
148784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
133 ms |
148472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
134 ms |
148344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
97528 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
97528 KB |
Output isn't correct |
| 3 |
Correct |
62 ms |
98168 KB |
Output is correct |
| 4 |
Incorrect |
59 ms |
97784 KB |
Output isn't correct |
| 5 |
Incorrect |
76 ms |
101624 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
97880 KB |
Output isn't correct |
| 2 |
Correct |
73 ms |
101500 KB |
Output is correct |
| 3 |
Runtime error |
142 ms |
148856 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
134 ms |
148216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
136 ms |
148216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
137 ms |
148392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
136 ms |
148088 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
133 ms |
148216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
140 ms |
148220 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
139 ms |
148984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
