oj.uz

Submission #261807

# Submission time Handle Problem Language Result Execution time Memory
261807 2020-08-12T05:34:11 Z oolimry Climbers (RMI18_climbers) C++14
0 / 100
 3 ms 640 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]) assert(false);
		if(H[i-1] < H[i] && H[i] < H[i+1]) assert(false);
		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];
		}
		
		ans += abs(H[pre.first] - H[cur.first]);
	}
	
	cout << ans;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)