oj.uz

Submission #837287

# Submission time Handle Problem Language Result Execution time Memory
837287 2023-08-25T09:15:11 Z gustason Soccer (JOI17_soccer) C++14
0 / 100
 932 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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);
}

int 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});

	while(!q.empty()) {
		auto v = q.top();
		q.pop();
		
		//cout << v.type << " " << v.cost << " " << v.x << " " << v.y << "\n";
		
		// 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 (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 (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";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8016 KB Output is correct
2 Correct 3 ms 7124 KB Output is correct
3 Runtime error 932 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 870 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8016 KB Output is correct
2 Correct 3 ms 7124 KB Output is correct
3 Runtime error 932 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -