제출 #36522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36522		UncleGrandpa925	Soccer (JOI17_soccer)	C++14	100 / 100	1246 ms	52788 KiB

soccer

/*input
4 6
0 5 1000
6
3 1
4 6
3 0
3 0
4 0
0 4

4 3
0 15 10
2
0 0
4 3

3 3
0 50 10
2
0 0
3 3

6 5
1 3 6
3
1 1
0 4
6 5
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define X first
#define Y second
#define mp make_pair
#define int long long
#define N
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}
struct data {
	int val, X, Y, mask, dir;
	data(int _val, int _X, int _Y, int _mask, int _dir): val(_val), X(_X), Y(_Y), mask(_mask), dir(_dir) {};
};

bool operator < (data a, data b) {
	return a.val > b.val;
}

int H, W;
int A, B, C, n;
vector<pair<int, int> > person;
int dp[505][505][4][4];
priority_queue<data> pq;
int dx[] = { -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void solve() {
	// 0 : ball with dir
	// 1 : ball only
	// 2 : person only
	// 3 : both
	dp[person[0].X][person[0].Y][3][0] = 0;
	pq.push(data(0, person[0].X, person[0].Y, 3, 0));
	for (int i = 1; i < person.size(); i++) {
		dp[person[i].X][person[i].Y][2][0] = 0;
		pq.push(data(0, person[i].X, person[i].Y, 2, 0));
	}
	while (!pq.empty()) {
		data top = pq.top(); pq.pop();
		if (dp[top.X][top.Y][top.mask][top.dir] != top.val) continue;
		if (top.mask == 2 || top.mask == 3) {
			for (int i = 0; i < 4; i++) { // person move
				int ax = top.X + dx[i];
				int ay = top.Y + dy[i];
				if (ax < 0 || ay < 0 || ax > H || ay > W) continue;
				if (dp[ax][ay][top.mask][0] > top.val + C) {
					dp[ax][ay][top.mask][0] = top.val + C;
					pq.push(data(top.val + C, ax, ay, top.mask, 0));
				}
			}
		}
		if (top.mask == 3) {
			if (dp[top.X][top.Y][2][0] > top.val) { // drop the ball
				dp[top.X][top.Y][2][0] = top.val;
				pq.push(data(top.val, top.X, top.Y, 2, 0));
			}
			if (dp[top.X][top.Y][1][0] > top.val) { // drop the ball
				dp[top.X][top.Y][1][0] = top.val;
				pq.push(data(top.val, top.X, top.Y, 1, 0));
			}
			for (int i = 0; i < 4; i++) { // kick the ball
				if (dp[top.X][top.Y][0][i] > top.val + B) {
					dp[top.X][top.Y][0][i] = top.val + B;
					pq.push(data(top.val + B, top.X, top.Y, 0, i));
				}
			}
		}
		else if (top.mask == 2) {
			if (dp[top.X][top.Y][3][0] > dp[top.X][top.Y][2][0] + dp[top.X][top.Y][1][0]) { // grab the ball
				dp[top.X][top.Y][3][0] = dp[top.X][top.Y][2][0] + dp[top.X][top.Y][1][0];
				pq.push(data(dp[top.X][top.Y][3][0], top.X, top.Y, 3, 0));
			}
		}
		else if (top.mask == 1) {
			if (dp[top.X][top.Y][3][0] > dp[top.X][top.Y][2][0] + dp[top.X][top.Y][1][0]) { // grab the ball
				dp[top.X][top.Y][3][0] = dp[top.X][top.Y][2][0] + dp[top.X][top.Y][1][0];
				pq.push(data(dp[top.X][top.Y][3][0], top.X, top.Y, 3, 0));
			}
		}
		else if (top.mask == 0) {
			if (dp[top.X][top.Y][1][0] > dp[top.X][top.Y][0][top.dir]) { // ball stop moving
				dp[top.X][top.Y][1][0] = dp[top.X][top.Y][0][top.dir];
				pq.push(data(dp[top.X][top.Y][1][0], top.X, top.Y, 1, 0));
			}
			int ax = top.X + dx[top.dir]; int ay = top.Y + dy[top.dir]; // ball keep moving
			if (0 <= ax and ax <= H and 0 <= ay and ay <= W and dp[ax][ay][0][top.dir] > top.val + A) {
				dp[ax][ay][0][top.dir] = top.val + A;
				pq.push(data(dp[ax][ay][0][top.dir], ax, ay, 0, top.dir));
			}
		}
	}
	int ans = 1e18;
	for (int x = 0; x <= H; x++) {
		for (int y = 0; y <= W; y++) {
			int dis = abs(x - person.back().X) + abs(y - person.back().Y);
			dis *= C;
			ans = min(ans, dis + dp[x][y][1][0]);
		}
	}
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> H >> W;
	cin >> A >> B >> C;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y; cin >> x >> y;
		person.push_back(mp(x, y));
	}
	memset(dp, 60, sizeof(dp));
	solve();
}

컴파일 시 표준 에러 (stderr) 메시지

soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
soccer.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
soccer.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
soccer.cpp: In function 'void solve()':
soccer.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < person.size(); i++) {
                    ^

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