oj.uz

Submission #670480

# Submission time Handle Problem Language Result Execution time Memory
670480 2022-12-09T08:22:05 Z Sohsoh84 Soccer (JOI17_soccer) C++17
35 / 100
 750 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pair<pll, int>> PX;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 500 + 10;

ll n, m, A, B, C, k, p_dist[MAXN][MAXN], SX, SY, TX, TY, dist[MAXN][MAXN][2];
queue<pll> q;
priority_queue<PX, vector<PX>, greater<PX>> pq;

inline void add_p(int x, int y, ll d) {
	if (x < 0 || y < 0 || x > n || y > m || p_dist[x][y] <= d) return;
	p_dist[x][y] = d;
	q.push({x, y});
}

inline void add(int x, int y, int b, ll d) {
	if (x < 0 || y < 0 || x > n || y > m || dist[x][y][b] <= d) return;
	dist[x][y][b] = d;
	pq.push({d, {{x, y}, b}});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> A >> B >> C >> k;

	memset(p_dist, 63, sizeof p_dist);
	for (int i = 1; i < k; i++) {
		int x, y;
		cin >> x >> y;
		if (i == 1) SX = x, SY = y;
		add_p(x, y, 0);
	}

	cin >> TX >> TY;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		ll d = p_dist[x][y];

		add_p(x - 1, y, d + 1);
		add_p(x + 1, y, d + 1);
		add_p(x, y - 1, d + 1);
		add_p(x, y + 1, d + 1);
	}

	memset(dist, 63, sizeof dist);
	add(SX, SY, 0, 0);

	while (!pq.empty()) {
		ll d = pq.top().X, x = pq.top().Y.X.X, y = pq.top().Y.X.Y, b = pq.top().Y.Y;
		pq.pop();
		if (d != dist[x][y][b]) continue;
	
		if (!b) {
			add(x, y, 1, d + p_dist[x][y] * C);
			continue;
		}

		add(x, y, 0, d);	
		add(x + 1, y, 1, d + C);
		add(x - 1, y, 1, d + C);
		add(x, y + 1, 1, d + C);
		add(x, y - 1, 1, d + C);
	
		for (int i = 0; i <= n; i++)
			add(i, y, 0, d + A * abs(x - i) + B);	
		for (int i = 0; i <= m; i++)
			add(x, i, 0, d + A * abs(y - i) + B);
	}


	cout << dist[TX][TY][0] << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8528 KB Output is correct
2 Correct 4 ms 7000 KB Output is correct
3 Correct 595 ms 14660 KB Output is correct
4 Correct 547 ms 14672 KB Output is correct
5 Correct 149 ms 8528 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 14712 KB Output is correct
2 Correct 685 ms 14776 KB Output is correct
3 Correct 412 ms 14768 KB Output is correct
4 Correct 556 ms 14700 KB Output is correct
5 Correct 513 ms 14776 KB Output is correct
6 Correct 573 ms 14748 KB Output is correct
7 Correct 643 ms 15028 KB Output is correct
8 Correct 577 ms 14748 KB Output is correct
9 Correct 750 ms 14964 KB Output is correct
10 Correct 64 ms 8600 KB Output is correct
11 Correct 616 ms 14836 KB Output is correct
12 Correct 612 ms 14772 KB Output is correct
13 Correct 373 ms 14752 KB Output is correct
14 Correct 628 ms 14900 KB Output is correct
15 Correct 521 ms 14904 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8528 KB Output is correct
2 Correct 4 ms 7000 KB Output is correct
3 Correct 595 ms 14660 KB Output is correct
4 Correct 547 ms 14672 KB Output is correct
5 Correct 149 ms 8528 KB Output is correct
6 Correct 650 ms 14712 KB Output is correct
7 Correct 685 ms 14776 KB Output is correct
8 Correct 412 ms 14768 KB Output is correct
9 Correct 556 ms 14700 KB Output is correct
10 Correct 513 ms 14776 KB Output is correct
11 Correct 573 ms 14748 KB Output is correct
12 Correct 643 ms 15028 KB Output is correct
13 Correct 577 ms 14748 KB Output is correct
14 Correct 750 ms 14964 KB Output is correct
15 Correct 64 ms 8600 KB Output is correct
16 Correct 616 ms 14836 KB Output is correct
17 Correct 612 ms 14772 KB Output is correct
18 Correct 373 ms 14752 KB Output is correct
19 Correct 628 ms 14900 KB Output is correct
20 Correct 521 ms 14904 KB Output is correct
21 Runtime error 290 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -