Submission #261812

#	Time	Username	Problem	Language	Result	Execution time	Memory
261812		oolimry	Climbers (RMI18_climbers)	C++14	25 / 100	142 ms	148984 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<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 (stderr)

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;
       ^~~~~

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