oj.uz

Submission #261808

# Submission time Handle Problem Language Result Execution time Memory
261808 2020-08-12T05:34:44 Z oolimry Climbers (RMI18_climbers) C++14
25 / 100
 800 ms 175224 KB 
#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 = 12345678901234567;

lint H[5005];
int n; 

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);
	
	n = sz(v);
	for(int i = 0;i < n;i++) H[i] = v[i];
	
	
	
	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;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 10 ms 384 KB Output is correct
5 Correct 41 ms 504 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 175096 KB Time limit exceeded
2 Execution timed out 1067 ms 163096 KB Time limit exceeded
3 Execution timed out 1078 ms 167984 KB Time limit exceeded
4 Execution timed out 1092 ms 150740 KB Time limit exceeded
5 Execution timed out 1087 ms 163636 KB Time limit exceeded

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 151252 KB Time limit exceeded
2 Execution timed out 1086 ms 169340 KB Time limit exceeded
3 Execution timed out 1086 ms 171312 KB Time limit exceeded
4 Execution timed out 1080 ms 168440 KB Time limit exceeded
5 Execution timed out 1088 ms 175224 KB Time limit exceeded
6 Execution timed out 1081 ms 172152 KB Time limit exceeded
7 Execution timed out 1093 ms 170588 KB Time limit exceeded
8 Execution timed out 1085 ms 166776 KB Time limit exceeded
9 Execution timed out 1097 ms 164628 KB Time limit exceeded
10 Execution timed out 1076 ms 159372 KB Time limit exceeded