oj.uz

Submission #491661

# Submission time Handle Problem Language Result Execution time Memory
491661 2021-12-03T18:26:39 Z valerikk Climbers (RMI18_climbers) C++17
20 / 100
 800 ms 327824 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5007;
const ll INF = 1e18;

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

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;
		}
	}

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

	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 (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[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[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[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]);
					}
				}
			}	
		}
	}

	ll ans = INF;
	for (int i = 0; i < n - 1; ++i) {
		ans = min(ans, d[i][i]);
		ans = min(ans, d[i + 1][i]);
	}

	cout << ans << endl;
	return 0;
}

Subtask #1
15.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 2124 KB Output is correct
3 Execution timed out 1092 ms 143764 KB Time limit exceeded
4 Execution timed out 1096 ms 214256 KB Time limit exceeded
5 Correct 151 ms 196392 KB Output is correct

Subtask #2
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Execution timed out 1090 ms 132100 KB Time limit exceeded
3 Execution timed out 1102 ms 132588 KB Time limit exceeded
4 Execution timed out 1093 ms 132360 KB Time limit exceeded
5 Execution timed out 1104 ms 134604 KB Time limit exceeded

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 132260 KB Time limit exceeded
2 Execution timed out 1090 ms 133604 KB Time limit exceeded
3 Execution timed out 1052 ms 143672 KB Time limit exceeded
4 Execution timed out 1103 ms 214312 KB Time limit exceeded
5 Execution timed out 1095 ms 214296 KB Time limit exceeded
6 Execution timed out 1101 ms 272964 KB Time limit exceeded
7 Execution timed out 1109 ms 273060 KB Time limit exceeded
8 Execution timed out 1114 ms 327720 KB Time limit exceeded
9 Execution timed out 1114 ms 327824 KB Time limit exceeded
10 Execution timed out 1061 ms 327804 KB Time limit exceeded