Submission #1053313

#TimeUsernameProblemLanguageResultExecution timeMemory
1053313n1kText editor (CEOI24_editor)C++17
56 / 100
3314 ms1048576 KiB
#include <bits/stdc++.h>

#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()

void solve(){
	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);

	// (cost, r, c)
	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 = 1e15;
	for(auto [c, cost]:row[er]){
		ans = min(ans, abs(ec - c) + cost);
	}
	cout << ans << endl;
	for(auto r:row){
		debug(r);
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t=1; //cin >> t;
	while(t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:58:3: note: in expansion of macro 'debug'
   58 |   debug(r);
      |   ^~~~~
#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...