Submission #1194390

#TimeUsernameProblemLanguageResultExecution timeMemory
1194390franuchText editor (CEOI24_editor)C++20
14 / 100
396 ms39620 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define vc vector
#define pub push_back
#define pob pop_back
#define st first
#define nd second
const ll INF = 1e18l;

void program() {
	ll n;
	cin >> n;
	ll si, sj, ti, tj;
	cin >> si >> sj >> ti >> tj;
	si--, sj--, ti--, tj--;
	vc<ll> a(n);
	for (ll &ai : a)
		cin >> ai;
	
	vc<vc<ll>> d(n);
	for (ll i = 0; i < n; i++)
		d[i].assign(a[i] + 1, INF);
	d[si][sj] = 0;
	
	queue<pll> tov;
	tov.push({si, sj});
	while (not tov.empty()) {
		auto [vi, vj] = tov.front();
		tov.pop();
		vc<pll> adj;
		if (vj + 1 <= a[vi])
			adj.pub({vi, vj + 1});
		else if (vi + 1 < n)
			adj.pub({vi + 1, 0});

		if (vj - 1 >= 0)
			adj.pub({vi, vj - 1});
		else if (vi - 1 >= 0)
			adj.pub({vi - 1, a[vi - 1]});

		if (vi + 1 < n)
			adj.pub({vi + 1, min(vj, a[vi + 1])});

		if (vi - 1 >= 0)
			adj.pub({vi - 1, min(vj, a[vi - 1])});

		for (auto &[wi, wj] : adj) {
			if (d[wi][wj] == INF) {
				d[wi][wj] = d[vi][vj] + 1;
				tov.push({wi, wj});
			}
		}
	}

	cout << d[ti][tj] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...