제출 #1194390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194390		franuch	Text editor (CEOI24_editor)	C++20	14 / 100	396 ms	39620 KiB

Main

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

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44