Submission #261833

#	Time	Username	Problem	Language	Result	Execution time	Memory
261833		oolimry	Climbers (RMI18_climbers)	C++14	40 / 100	407 ms	166392 KiB

climbers

#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;
}

• Subtask 1: 25 / 25
• Subtask 2: 10 / 25
• Subtask 3: 5 / 50