Submission #1227089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227089		chaeryeong	Soccer (JOI17_soccer)	C++20	35 / 100	3002 ms	103344 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int h, w;
ll A, B, C;
int n;
ll a[100001][2];
int vis[502][502];
ll dist[502][502]; //person at (i, j)
ll dist2[502][502][4]; //ball with persons at (i, j) and being shot
ll dist3[502][502]; //nobody at (i, j)
ll dist4[502][502][4]; //ball alone at (i, j) and being shot
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
bool check (int x, int y) {
	return x >= 0 && x <= h && y >= 0 && y <= w;
}
void solve () {
	cin >> h >> w >> A >> B >> C;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][0] >> a[i][1];
		vis[a[i][0]][a[i][1]] = i;
	}
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			dist[i][j] = dist3[i][j] = inf;
			for (int k = 0; k < 4; k++) {
				dist2[i][j][k] = dist4[i][j][k] = inf;
			}
		}
	}
	priority_queue <array <ll, 5>, vector <array <ll, 5>>, greater <>> pq;
	auto relax = [&] (array <ll, 5> x) -> void {
		if (x[4] == 1) {
			if (x[0] < dist[x[1]][x[2]]) {
				dist[x[1]][x[2]] = x[0];
				pq.push(x);
			}
 		} else if (x[4] == 2) {
 			if (x[0] < dist2[x[1]][x[2]][x[3]]) {
 				pq.push(x);
 				dist2[x[1]][x[2]][x[3]] = x[0];
 			}
 		} else if (x[4] == 3) {
 			if (x[0] < dist3[x[1]][x[2]]) {
 				dist3[x[1]][x[2]] = x[0];
 				pq.push(x);
 			}
 		} else {
 			if (x[0] < dist4[x[1]][x[2]][x[3]]) {
 				pq.push(x);
 				dist4[x[1]][x[2]][x[3]] = x[0];
 			}
 		}
 	};
 	relax({0, a[1][0], a[1][1], -1, 1});
	while (!pq.empty()) {
		auto x = pq.top();
		pq.pop();
		if (x[4] == 1) {
			if (x[0] > dist[x[1]][x[2]]) {
				continue;
			}
			for (int i = 0; i < 4; i++) {
				if (check(x[1] + dx[i], x[2] + dy[i])) {
					relax({x[0] + C, x[1] + dx[i], x[2] + dy[i], -1, 1});
				}
			}
			relax({x[0], x[1], x[2], -1, 3});
			for (auto i : {0, 1, 2, 3}) {
				relax({x[0] + B, x[1], x[2], i, 2});
				relax({x[0] + B, x[1], x[2], i, 4});
			}
 		} else if (x[4] == 2) {
 			if (x[0] > dist2[x[1]][x[2]][x[3]]) {
 				continue;
 			}
 			if (x[3] == 0 && check(x[1] - 1, x[2])) {
 				relax({x[0] + A + C, x[1] - 1, x[2], x[3], 2});
 			}
  			if (x[3] == 1 && check(x[1] + 1, x[2])) {
 				relax({x[0] + A + C, x[1] + 1, x[2], x[3], 2});
 			}
 			if (x[3] == 2 && check(x[1], x[2] - 1)) {
 				relax({x[0] + A + C, x[1], x[2] - 1, x[3], 2});
 			}
  			if (x[3] == 3 && check(x[1], x[2] + 1)) {
 				relax({x[0] + A + C, x[1], x[2] + 1, x[3], 2});
 			}
 			relax({x[0], x[1], x[2], -1, 1});
 		} else if (x[4] == 3) {
 			if (x[0] > dist3[x[1]][x[2]]) {
 				continue;
 			}
			for (int i = 1; i <= n; i++) {
				relax({x[0] + C * abs(a[i][0] - x[1]) + C * abs(a[i][1] - x[2]), x[1], x[2], -1, 1});
			}

 		} else {
 			if (x[0] > dist4[x[1]][x[2]][x[3]]) {
 				continue;
 			}
 			if (x[3] == 0 && check(x[1] - 1, x[2])) {
 				relax({x[0] + A, x[1] - 1, x[2], x[3], 4});
 			}
  			if (x[3] == 1 && check(x[1] + 1, x[2])) {
 				relax({x[0] + A, x[1] + 1, x[2], x[3], 4});
 			}
 			if (x[3] == 2 && check(x[1], x[2] - 1)) {
 				relax({x[0] + A, x[1], x[2] - 1, x[3], 4});
 			}
  			if (x[3] == 3 && check(x[1], x[2] + 1)) {
 				relax({x[0] + A, x[1], x[2] + 1, x[3], 4});
 			}
 			relax({x[0], x[1], x[2], -1, 3});
 		}
	}
	cout << min(dist[a[n][0]][a[n][1]], dist3[a[n][0]][a[n][1]]) << '\n';
}	
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65