oj.uz

Submission #261795

# Submission time Handle Problem Language Result Execution time Memory
261795 2020-08-12T05:20:25 Z oolimry Climbers (RMI18_climbers) C++14
0 / 100
 800 ms 384 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;
	}
	
	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{
			pre =  cur;
			cur = res[0];
		}
		
		ans += abs(H[pre.first] - H[cur.first]);
	}
	
	cout << ans;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Execution timed out 1093 ms 384 KB Time limit exceeded
5 Incorrect 8 ms 384 KB Output isn't correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 256 KB Time limit exceeded
2 Execution timed out 1092 ms 384 KB Time limit exceeded
3 Execution timed out 1088 ms 384 KB Time limit exceeded
4 Execution timed out 1088 ms 384 KB Time limit exceeded
5 Execution timed out 1088 ms 384 KB Time limit exceeded

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 384 KB Time limit exceeded
2 Execution timed out 1088 ms 384 KB Time limit exceeded
3 Execution timed out 1085 ms 384 KB Time limit exceeded
4 Execution timed out 1058 ms 384 KB Time limit exceeded
5 Execution timed out 1099 ms 384 KB Time limit exceeded
6 Execution timed out 1097 ms 384 KB Time limit exceeded
7 Execution timed out 1088 ms 384 KB Time limit exceeded
8 Execution timed out 1089 ms 384 KB Time limit exceeded
9 Execution timed out 1079 ms 384 KB Time limit exceeded
10 Execution timed out 1083 ms 384 KB Time limit exceeded