#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<int,int> ii;
const lint inf = 123456789;
lint H[5005];
int n;
int to(int peak, int slope){
return peak * 6000 + slope;
}
int dis[31000000];
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;
int w = abs(H[pu] - H[pv]);
adj[u].push_back(ii(w,v));
adj[v].push_back(ii(w,u));
}
vector<ii> trans(int peak, int slope){
vector<ii> res;
if(peak&1){ ///is peak
int slopeEnd;
if(slope & 1) slopeEnd = slope+1;
else slopeEnd = slope;
///go right
if(H[slopeEnd] >= H[peak+1]){
ii nxt = ii(slopeEnd, peak);
res.push_back(ii(nxt));
}
else{
ii nxt = ii(peak+1, slope);
res.push_back(ii(nxt));
}
///go left
if(H[slopeEnd] >= H[peak-1]){
ii nxt = ii(slopeEnd, peak-1);
res.push_back(ii(nxt));
}
else{
ii nxt = ii(peak-1, slope);
res.push_back(ii(nxt));
}
}
else{ ///is valley
int slopeEnd;
if(slope & 1) slopeEnd = slope;
else slopeEnd = slope + 1;
///go right
if(H[slopeEnd] <= H[peak+1]){
ii nxt = ii(slopeEnd, peak);
res.push_back(ii(nxt));
}
else{
ii nxt = ii(peak+1, slope);
res.push_back(ii(nxt));
}
///go left
if(H[slopeEnd] <= H[peak-1]){
ii nxt = ii(slopeEnd, peak-1);
res.push_back(ii(nxt));
}
else{
ii nxt = ii(peak-1, slope);
res.push_back(ii(nxt));
}
}
return res;
}
vector<ii> trans(ii c){ return trans(c.first, c.second); }
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);
set<int> SS;
n = sz(v);
for(int i = 0;i < n;i++) H[i] = v[i];
for(int i = 0;i < n-1;i++) SS.insert(v[i]);
if(sz(SS) == n-1){
if(H[1] > H[n-2]) reverse(H,H+n);
ii pre = ii(n-1, 0);
ii cur = ii(1, n-2);
lint ans = H[1];
int ctr = 0;
while(true){
ctr++;
//if(ctr >= 400000000) break;
if(cur.first == cur.second || cur.first == cur.second + 1) break;
vector<ii> res = trans(cur);
if(res[0] == pre){
pre = cur;
cur = res[1];
}
else if(res[1] == pre){
pre = cur;
cur = res[0];
}
else cout << "fjdsifjsdifjdsklfjdkf\n";
ans += abs(H[pre.first] - H[cur.first]);
}
cout << ans;
return 0;
}
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));
}
}
}
int 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:244:9: warning: unused variable 'npeak' [-Wunused-variable]
int npeak = nei.second / 6000;
^~~~~
climbers.cpp:245:9: warning: unused variable 'nslope' [-Wunused-variable]
int nslope = nei.second % 6000;
^~~~~~
climbers.cpp:237:7: warning: unused variable 'peak' [-Wunused-variable]
int peak = cur.second / 6000;
^~~~
climbers.cpp:238:7: warning: unused variable 'slope' [-Wunused-variable]
int slope = cur.second % 6000;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
73080 KB |
Output is correct |
| 2 |
Correct |
52 ms |
73216 KB |
Output is correct |
| 3 |
Correct |
50 ms |
73212 KB |
Output is correct |
| 4 |
Correct |
64 ms |
73336 KB |
Output is correct |
| 5 |
Correct |
97 ms |
73464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
85240 KB |
Output is correct |
| 2 |
Incorrect |
60 ms |
85368 KB |
Output isn't correct |
| 3 |
Correct |
60 ms |
85752 KB |
Output is correct |
| 4 |
Incorrect |
58 ms |
85504 KB |
Output isn't correct |
| 5 |
Incorrect |
72 ms |
87800 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
85624 KB |
Output isn't correct |
| 2 |
Correct |
71 ms |
87800 KB |
Output is correct |
| 3 |
Incorrect |
344 ms |
138424 KB |
Output isn't correct |
| 4 |
Runtime error |
165 ms |
148600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
164 ms |
148216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
164 ms |
148988 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
141 ms |
148216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
147 ms |
148728 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
141 ms |
148344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
155 ms |
152312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
