Submission #1302214

#TimeUsernameProblemLanguageResultExecution timeMemory
1302214vlomaczkSoccer (JOI17_soccer)C++20
0 / 100
466 ms26452 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll H,W;
	cin >> H >> W;
	ll A,B,C;
	cin >> A >> B >> C;
	ll n; cin >> n;
	vector<set<ll>> rows(H+1);
	vector<int> row(n), col(n);
	for(ll i=0; i<n; ++i) {
		cin >> row[i] >> col[i];
		rows[row[i]].insert(col[i]);
	}
	ll inf = 1e18;
	vector<vector<ll>> closest_in_row(H+1, vector<ll>(W+1, 1e6));	
	for(ll r=0; r<=H; ++r) {
		for(ll c=0; c<=W; ++c) {
			auto hi = rows[r].upper_bound(c);
			if(hi!=rows[r].end()) {
				closest_in_row[r][c] = min(closest_in_row[r][c], (*hi)-c);
			}
			if(hi!=rows[r].begin()) {
				auto lo = hi;
				--lo;
				closest_in_row[r][c] = min(closest_in_row[r][c], c-(*lo));
			}
		}
	}
	vector<vector<ll>> closest(H+1,vector<ll>(W+1, 1e6));	
	for(ll r=0; r<=H; ++r) {
		for(ll c=0; c<=W; ++c) {
			for(int r2=0; r2<=H; ++r2) {
				closest[r][c] = min(closest[r][c], abs(r-r2) + closest_in_row[r2][c]);
			}
		}
	}
	vector<vector<vector<ll>>> dist(H+1, vector<vector<ll>>(W+1, vector<ll>(3, inf)));
	priority_queue<pair<int, pair<pair<int, int>, int>>> pq;
	auto check = [&](int r, int c, int m, int d) {
		if(r < 0 || r > H || c < 0 || c > W) return;
		if(dist[r][c][m] > d) {
			dist[r][c][m] = d;
			pq.push({-d, {{r,c},m}});
		}
	};
	dist[row[0]][col[0]][0] = 0;
	pq.push({0, {{row[0], col[0]}, 0}});
	while(pq.size()) {
		auto[dv, stat] = pq.top(); pq.pop();
		dv*=-1;
		auto[pos, mode] = stat;
		auto[r,c] = pos;
		if(dist[r][c][mode] != dv) continue;
		if(mode==0) {
			check(r+1, c, 0, dv+C);
			check(r-1, c, 0, dv+C);
			check(r, c+1, 0, dv+C);
			check(r, c-1, 0, dv+C);
			
			check(r, c, 1, dv+B);
			check(r, c, 2, dv+B);
		} else if(mode==1) {
			check(r+1, c, 1, dv+A);
			check(r-1, c, 1, dv+A);
		} else {
			check(r, c+1, 2, dv+A);
			check(r, c-1, 2, dv+A);
		}
		if(mode) check(r,c,0,dv + C*closest[r][c]);
	}
	int r = row[n-1];
	int c = col[n-1];
	cout << min(dist[r][c][0], min(dist[r][c][1], dist[r][c][2])) << "\n";


	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...