Submission #491673

#	Time	Username	Problem	Language	Result	Execution time	Memory
491673		valerikk	Climbers (RMI18_climbers)	C++17	100 / 100	208 ms	196308 KiB

climbers

#include <bits/stdc++.h>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

const int N = 5007;
const ull INF = numeric_limits<ull>::max();

int n;
ull h[N];
ull d[N][N];

priority_queue<pair<ull, pair<int, int>>, vector<pair<ull, pair<int, int>>>, greater<pair<ull, pair<int, int>>>> q;
	
void upd(int i, int j, ull dd) {
	if (dd < d[i][j]) {
		d[i][j] = dd;
		q.push({dd, {i, j}});
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n - 1; ++j) {
			d[i][j] = INF;
		}
	}

	upd(0, n - 2, 0);

	while (!q.empty()) {
		auto z = q.top();
		q.pop();

		auto [i, j] = z.second;
	
		if (d[i][j] != z.first) {
			continue;
		}

		if (i == j || i - 1 == j) {
			cout << d[i][j] << endl;
			return 0;
		}

		if (h[i] == h[j]) {
			if (j > 0) {
				upd(i, j - 1, d[i][j]);
			}
			upd(j, i, d[i][j]);
		}

		if (h[i] == h[j + 1]) {
			if (j < n - 1) {
				upd(i, j + 1, d[i][j]);
			}
			upd(j + 1, i, d[i][j]);
		}

		for (int ii : {i - 1, i + 1}) {
			if (ii < 0 || n <= ii) {
				continue;
			}

			if (h[i] < h[ii]) {
				if (h[i] < h[j]) {
					if (h[ii] - h[i] <= h[j] - h[i]) {
						upd(ii, j, d[i][j] + h[ii] - h[i]);
					} else {
						upd(j, min(ii, i), d[i][j] + h[j] - h[i]);
					}
				} else {
					if (h[i] < h[j + 1]) {
						if (h[ii] - h[i] <= h[j + 1] - h[i]) {
							upd(ii, j, d[i][j] + h[ii] - h[i]);
						} else {
							upd(j + 1, min(ii, i), d[i][j] + h[j + 1] - h[i]);
						}
					}
				}
			}

			if (h[i] > h[ii]) {
				if (h[i] > h[j]) {
					if (h[i] - h[ii] <= h[i] - h[j]) {
						upd(ii, j, d[i][j] + h[i] - h[ii]);
					} else {
						upd(j, min(ii, i), d[i][j] + h[i] - h[j]);
					}
				} else {
					if (h[i] > h[j + 1]) {
						if (h[i] - h[ii] <= h[i] - h[j + 1]) {
							upd(ii, j, d[i][j] + h[i] - h[ii]);
						} else {
							upd(j + 1, min(ii, i), d[i][j] + h[i] - h[j + 1]);
						}
					}
				}
			}	
		}
	}

	cout << "NO" << endl;
	return 0;
}

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