oj.uz

Submission #837307

# Submission time Handle Problem Language Result Execution time Memory
837307 2023-08-25T09:30:37 Z gustason Soccer (JOI17_soccer) C++14
35 / 100
 3000 ms 16596 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

const ll INF = 1e16 + 5;
const int INF2 = 1e9 + 5;

int dist[501][501];
ll cost[3][501][501];

struct Vertex {
	int type, x, y;
	ll cost;
	bool operator<(const Vertex& other) const {
		return cost > other.cost;
	}
};

void fill() {
	for(int i = 0; i < 501; i++) {
		for(int j = 0; j < 501; j++) {
			dist[i][j] = INF2;
			for(int k = 0; k < 3; k++) {
				cost[k][i][j] = INF;
			}
		}
	}
}

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

void mini(int& a, int b) {
	a = min(a, b);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int H, W, A, B, C;
	cin >> H >> W >> A >> B >> C;
	
	auto gali = [&](int X, int Y) {
		return (X >= 0 && X <= H && Y >= 0 && Y <= W);
	};
	
	int n;
	cin >> n;
	
	fill();
	
	vector<array<int, 2>> p(n);
	for(auto& i : p) {
		cin >> i[0] >> i[1];
	}
	
	for(int i = 0; i <= H; i++) {
		for(int j = 0; j <= W; j++) {
			for(int k = 0; k < n; k++) {
				dist[i][j] = min(dist[i][j], abs(p[k][0] - i) + abs(p[k][1] - j));
			}
		}
	}
	
	priority_queue<Vertex> q;
	q.push({2, p[0][0], p[0][1], 0});
	cost[2][p[0][0]][p[0][1]] = 0;

	while(!q.empty()) {
		auto v = q.top();
		q.pop();
		
		//cout << v.type << " " << v.cost << " " << v.x << " " << v.y << "\n";
		
		if (v.cost != cost[v.type][v.x][v.y]) continue;
		
		// moving w/ ball
		if (v.type == 2) {
			if (v.cost + B < cost[0][v.x][v.y]) {
				cost[0][v.x][v.y] = v.cost + B;
				q.push({0, v.x, v.y, v.cost + B});
			}
			if (v.cost + B < cost[1][v.x][v.y]) {
				cost[1][v.x][v.y] = v.cost + B;
				q.push({1, v.x, v.y, v.cost + B});
			}
			
			for(int d = 0; d < 4; d++) {
				int X = v.x + dx[d];
				int Y = v.y + dy[d];
				
				if (!gali(X, Y)) continue; 
				
				if (v.cost + C < cost[2][X][Y]) {
					cost[2][X][Y] = v.cost + C;
					q.push({2, X, Y, v.cost + C});
				}
			}
		}
		// kick in x
		else if (v.type == 1) {
			if (gali(v.x+1, v.y) && v.cost + A < cost[1][v.x+1][v.y]) {
				cost[1][v.x+1][v.y] = v.cost + A;
				q.push({1, v.x+1, v.y, v.cost + A});
			}
			if (gali(v.x-1, v.y) && v.cost + A < cost[1][v.x-1][v.y]) {
				cost[1][v.x-1][v.y] = v.cost + A;
				q.push({1, v.x-1, v.y, v.cost + A});
			}
			if (v.cost + C * dist[v.x][v.y] < cost[2][v.x][v.y]) {
				cost[2][v.x][v.y] = v.cost + C * dist[v.x][v.y];
				q.push({2, v.x, v.y, v.cost + C * dist[v.x][v.y]});
			}
		}
		// kick in Y
		else {
			if (gali(v.x, v.y+1) && v.cost + A < cost[0][v.x][v.y+1]) {
				cost[0][v.x][v.y+1] = v.cost + A;
				q.push({0, v.x, v.y+1, v.cost + A});
			}
			if (gali(v.x, v.y-1) && v.cost + A < cost[0][v.x][v.y-1]) {
				cost[0][v.x][v.y-1] = v.cost + A;
				q.push({0, v.x, v.y-1, v.cost + A});
			}
			if (v.cost + C * dist[v.x][v.y] < cost[2][v.x][v.y]) {
				cost[2][v.x][v.y] = v.cost + C * dist[v.x][v.y];
				q.push({2, v.x, v.y, v.cost + C * dist[v.x][v.y]});
			}
		}
	}
	
	cout << cost[2][p.back()[0]][p.back()[1]] << "\n";
	//for(int i = 0; i < n; i++) {
		//cout << cost[2][p[i][0]][p[i][1]] << "\n";
	//}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10320 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 173 ms 16492 KB Output is correct
4 Correct 192 ms 16476 KB Output is correct
5 Correct 30 ms 8288 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 16452 KB Output is correct
2 Correct 200 ms 16464 KB Output is correct
3 Correct 157 ms 16500 KB Output is correct
4 Correct 157 ms 16452 KB Output is correct
5 Correct 229 ms 16508 KB Output is correct
6 Correct 482 ms 16484 KB Output is correct
7 Correct 497 ms 16500 KB Output is correct
8 Correct 510 ms 16480 KB Output is correct
9 Correct 523 ms 16480 KB Output is correct
10 Correct 81 ms 10360 KB Output is correct
11 Correct 506 ms 16484 KB Output is correct
12 Correct 205 ms 16472 KB Output is correct
13 Correct 383 ms 16484 KB Output is correct
14 Correct 511 ms 16488 KB Output is correct
15 Correct 412 ms 16548 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10320 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 173 ms 16492 KB Output is correct
4 Correct 192 ms 16476 KB Output is correct
5 Correct 30 ms 8288 KB Output is correct
6 Correct 200 ms 16452 KB Output is correct
7 Correct 200 ms 16464 KB Output is correct
8 Correct 157 ms 16500 KB Output is correct
9 Correct 157 ms 16452 KB Output is correct
10 Correct 229 ms 16508 KB Output is correct
11 Correct 482 ms 16484 KB Output is correct
12 Correct 497 ms 16500 KB Output is correct
13 Correct 510 ms 16480 KB Output is correct
14 Correct 523 ms 16480 KB Output is correct
15 Correct 81 ms 10360 KB Output is correct
16 Correct 506 ms 16484 KB Output is correct
17 Correct 205 ms 16472 KB Output is correct
18 Correct 383 ms 16484 KB Output is correct
19 Correct 511 ms 16488 KB Output is correct
20 Correct 412 ms 16548 KB Output is correct
21 Correct 31 ms 8540 KB Output is correct
22 Correct 227 ms 16468 KB Output is correct
23 Correct 259 ms 12380 KB Output is correct
24 Correct 714 ms 12404 KB Output is correct
25 Correct 1302 ms 16596 KB Output is correct
26 Execution timed out 3057 ms 12548 KB Time limit exceeded
27 Halted 0 ms 0 KB -