Submission #261822

#	Time	Username	Problem	Language	Result	Execution time	Memory
261822		oolimry	Climbers (RMI18_climbers)	C++14	40 / 100	344 ms	152312 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 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 (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: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;
       ^~~~~

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