Submission #1220221

#TimeUsernameProblemLanguageResultExecution timeMemory
1220221MateiKing80Text editor (CEOI24_editor)C++20
56 / 100
4126 ms782244 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second

vector<int> len;
int n, t_idx;

int wiggle(int newF) {
	 int to_add = abs(newF - t_idx);
	 to_add = min(to_add, abs(min(newF + len[0], len[0] * n) - t_idx) + 1);
	 if (newF - len[0] >= 0)
		  to_add = min(to_add, abs(max(0LL, newF - len[0]) - t_idx) + 1);
	 return to_add;
}

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int sr, sc, er, ec; 
	cin >> n >> sr >> sc >> er >> ec;
	sr --, sc --, er --, ec --;
	vector<int> l(n);
	for (int i = 0; i < n; i ++) 
		cin >> l[i];
 
	vector<map<int, int>> row(n);
 
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
	pq.push({0, sr, sc});
	while(pq.size()) {
		auto [cost, r, c] = pq.top();
		pq.pop();
		if (row[r].count(c))
			continue;
		row[r][c] = cost;
		if (c == 0 && r != 0)
			pq.push({cost + 1, r - 1, l[r - 1]});
		if (c == l[r] && r != n - 1)
			pq.push({cost + 1, r + 1, 0});
		pq.push({cost + c, r, 0});
		pq.push({cost + l[r] - c, r, l[r]});
		pq.push({cost + l[r] - c, r, l[r]});
		if (r != 0)
			pq.push({cost + 1, r - 1, min(l[r - 1], c)});
		if (r != n - 1)
			pq.push({cost + 1, r + 1, min(l[r + 1], c)});
	}
	int ans = 1e18;
	for (auto [c, cost] : row[er])
		ans = min(ans, abs(ec - c) + cost);
	cout << ans;
}
#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...