oj.uz

Submission #532865

# Submission time Handle Problem Language Result Execution time Memory
532865 2022-03-04T06:19:47 Z rk42745417 Soccer (JOI17_soccer) C++17
100 / 100
 568 ms 26868 KB 
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(4e18) + ll(2e15);
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main() {
	int h, w;
	cin >> h >> w;
	auto check = [&](int a, int b) {
		return a >= 0 && a <= h && b >= 0 && b <= w;
	};

	ll a, b, c;
	cin >> a >> b >> c;
	int n;
	cin >> n;
	vector<pair<int, int>> arr(n);
	for(int i = 0; i < n; i++)
		cin >> arr[i].first >> arr[i].second;

	vector<vector<int>> dis(h + 1, vector<int>(w + 1, INF));
	for(const auto &[x, y] : arr)
		dis[x][y] = 0;
	queue<pair<int, int>> bfs;
	for(int i = 0; i <= h; i++)
		for(int j = 0; j <= w; j++)
			if(dis[i][j] == 0)
				bfs.push({i, j});
	while(!bfs.empty()) {
		auto [u, v] = bfs.front();
		bfs.pop();
		for(int i = 0; i < 4; i++) {
			int x = u + dx[i], y = v + dy[i];
			if(check(x, y) && dis[x][y] > dis[u][v] + 1)
				dis[x][y] = dis[u][v] + 1, bfs.push({x, y});
		}
	}

	vector<vector<vector<ll>>> ans(h + 1, vector<vector<ll>>(w + 1, vector<ll>(5, LINF)));
	ans[arr[0].first][arr[0].second][0] = 0;
	priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq;
	pq.push({0, arr[0].first, arr[0].second, 0});
	while(!pq.empty()) {
		auto [d, u, v, w] = pq.top();
		pq.pop();
		if(d > ans[u][v][w])
			continue;
		ll cost = 0;
		if(w == 0) {
			for(int i = 1; i <= 4; i++) {
				if(ans[u][v][i] > ans[u][v][w] + b) {
					ans[u][v][i] = ans[u][v][w] + b;
					pq.push({ans[u][v][i], u, v, i});
				}
			}
			cost = c;
		}
		else {
			if(ans[u][v][0] > ans[u][v][w] + c * dis[u][v]) {
				ans[u][v][0] = ans[u][v][w] + c * dis[u][v];
				pq.push({ans[u][v][0], u, v, 0});
			}
			cost = a;
		}
		for(int i = 0; i < 4; i++) {
			int x = u + dx[i], y = v + dy[i];
			if((w == 0 || i + 1 == w) && check(x, y) && ans[x][y][w] > d + cost) {
				ans[x][y][w] = d + cost;
				pq.push({ans[x][y][w], x, y, w});
			}
		}
	}

	ll ret = LINF;
	for(int i = 0; i <= h; i++)
		for(int j = 0; j <= w; j++)
			for(int k = 0; k < 2; k++)
				ret = min(ret, ans[i][j][k] + c * (abs(i - arr[n - 1].first) + abs(j - arr[n - 1].second)));
	cout << ret << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 6468 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 342 ms 25240 KB Output is correct
4 Correct 409 ms 25260 KB Output is correct
5 Correct 76 ms 7224 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 25276 KB Output is correct
2 Correct 449 ms 25300 KB Output is correct
3 Correct 315 ms 21576 KB Output is correct
4 Correct 291 ms 25236 KB Output is correct
5 Correct 301 ms 21508 KB Output is correct
6 Correct 323 ms 25256 KB Output is correct
7 Correct 419 ms 25292 KB Output is correct
8 Correct 407 ms 25292 KB Output is correct
9 Correct 427 ms 25324 KB Output is correct
10 Correct 64 ms 5052 KB Output is correct
11 Correct 424 ms 25384 KB Output is correct
12 Correct 400 ms 25272 KB Output is correct
13 Correct 234 ms 21576 KB Output is correct
14 Correct 426 ms 25260 KB Output is correct
15 Correct 326 ms 21512 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 6468 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 342 ms 25240 KB Output is correct
4 Correct 409 ms 25260 KB Output is correct
5 Correct 76 ms 7224 KB Output is correct
6 Correct 439 ms 25276 KB Output is correct
7 Correct 449 ms 25300 KB Output is correct
8 Correct 315 ms 21576 KB Output is correct
9 Correct 291 ms 25236 KB Output is correct
10 Correct 301 ms 21508 KB Output is correct
11 Correct 323 ms 25256 KB Output is correct
12 Correct 419 ms 25292 KB Output is correct
13 Correct 407 ms 25292 KB Output is correct
14 Correct 427 ms 25324 KB Output is correct
15 Correct 64 ms 5052 KB Output is correct
16 Correct 424 ms 25384 KB Output is correct
17 Correct 400 ms 25272 KB Output is correct
18 Correct 234 ms 21576 KB Output is correct
19 Correct 426 ms 25260 KB Output is correct
20 Correct 326 ms 21512 KB Output is correct
21 Correct 83 ms 7556 KB Output is correct
22 Correct 482 ms 25212 KB Output is correct
23 Correct 493 ms 20416 KB Output is correct
24 Correct 530 ms 22200 KB Output is correct
25 Correct 419 ms 25284 KB Output is correct
26 Correct 450 ms 25396 KB Output is correct
27 Correct 266 ms 20380 KB Output is correct
28 Correct 274 ms 20812 KB Output is correct
29 Correct 385 ms 23752 KB Output is correct
30 Correct 224 ms 20660 KB Output is correct
31 Correct 433 ms 25272 KB Output is correct
32 Correct 568 ms 26868 KB Output is correct
33 Correct 370 ms 25296 KB Output is correct
34 Correct 563 ms 25288 KB Output is correct
35 Correct 232 ms 20920 KB Output is correct