#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 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(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];
}
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(H[peak] == H[slope]){
//addEdge(slope,peak);
int aL = H[peak-1];
int aR = H[peak+1];
int bL = H[slope-1];
int bR = H[slope+1];
if(peak&1){ /// is peak
if(aL >= bL) addEdge(peak-1,slope-1);
if(aL >= bR) addEdge(peak-1, slope);
if(bL >= aL) addEdge(slope-1, peak-1);
if(bL >= aR) addEdge(slope-1, peak);
}
else{
if(aL <= bL) addEdge(peak-1,slope-1);
if(aL <= bR) addEdge(peak-1, slope);
if(bL <= aL) addEdge(slope-1, peak-1);
if(bL <= aR) addEdge(slope-1, peak);
}
}
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();
for(ii nei : adj[cur.second]){
if(dis[nei.second] > nei.first + cur.first){
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
73080 KB |
Output is correct |
| 2 |
Correct |
50 ms |
73080 KB |
Output is correct |
| 3 |
Correct |
50 ms |
73208 KB |
Output is correct |
| 4 |
Correct |
59 ms |
73336 KB |
Output is correct |
| 5 |
Correct |
111 ms |
73448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
85240 KB |
Output is correct |
| 2 |
Incorrect |
57 ms |
85376 KB |
Output isn't correct |
| 3 |
Correct |
79 ms |
85880 KB |
Output is correct |
| 4 |
Incorrect |
71 ms |
85624 KB |
Output isn't correct |
| 5 |
Incorrect |
93 ms |
88336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
85896 KB |
Output isn't correct |
| 2 |
Correct |
96 ms |
89176 KB |
Output is correct |
| 3 |
Incorrect |
407 ms |
166392 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 |
145 ms |
148240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
145 ms |
149068 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
146 ms |
148216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
143 ms |
148600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
145 ms |
148412 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
154 ms |
152184 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
