Submission #1069029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069029		faruk	Text editor (CEOI24_editor)	C++17	56 / 100	4048 ms	1048576 KiB

Main

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

vector<ll> len;
ll n;
ll f_idx, t_idx;

ll wiggle(ll f_idx) {
    ll to_add = abs(f_idx - t_idx);
    to_add = min(to_add, abs(min(f_idx + len[0], len[0]*((ll)n - 1)) - t_idx) + 1);
    if (f_idx - len[0] >= 0)
        to_add = min(to_add, abs(max(0LL, f_idx - len[0]) - t_idx) + 1);
    return to_add;
}
 
int main() {
	cin.tie(0);
  	ios_base::sync_with_stdio(0);
	int n, sr, sc, er, ec; cin >> n >> sr >> sc >> er >> ec;
	vector<ll> l(n);
	for(int i=0; i<n; i++) cin >> l[i];
	sr--, sc--, er--, ec--;
 
	vector<map<int, ll>> row(n);
 
	priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 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 begin
		if(c==0 and r!=0){
			pq.push({cost + 1, r-1, l[r-1]});
		}
		// if end
		if(c==l[r] and r!=n-1){
			pq.push({cost + 1, r + 1, 0});
		}
		// mid
		// go left, right, up, down
		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)});
		}
	}
	ll ans = 1e18;
	for(auto [c, cost]:row[er]){
		ans = min(ans, abs(ec - c) + cost);
	}
	cout << ans << endl;

}

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