Submission #141071

#	Time	Username	Problem	Language	Result	Execution time	Memory
141071		DrumpfTheGodEmperor	Soccer (JOI17_soccer)	C++14	35 / 100	2170 ms	262144 KiB

soccer

#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5, BOARD = 505;
int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
int h, w, a, b, c, n, s[N], t[N], nearest[BOARD][BOARD], ans[BOARD][BOARD];
queue<pair<int, int>> bfsQueue;
priority_queue<iii, vector<iii>, greater<iii>> pq;
bool check(int i, int j) {
	return i >= 0 && j >= 0 && i < h && j < w;
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> h >> w >> a >> b >> c >> n;
	h++, w++;
	memset(nearest, 63, sizeof nearest);
	memset(ans, 63, sizeof ans);
	fw (i, 0, n) {
		cin >> s[i] >> t[i];
		nearest[s[i]][t[i]] = 0;
		bfsQueue.push(ii(s[i], t[i]));
	}
	while (!bfsQueue.empty()) {
		ii curCoords = bfsQueue.front(); bfsQueue.pop();
		int curI = curCoords.fi, curJ = curCoords.se;
		fw (i, 0, 4) {
			int nxtI = curI + dx[i], nxtJ = curJ + dy[i];
			if (!check(nxtI, nxtJ)) continue;
			if (nearest[nxtI][nxtJ] <= nearest[curI][curJ] + 1) continue;
//			cout << "Fix " << nxtI << " " << nxtJ << " old nearest = " << nearest[nxtI][nxtJ] << " cur nearest = " << nearest[curI][curJ] << "\n";
			nearest[nxtI][nxtJ] = nearest[curI][curJ] + 1;
			bfsQueue.push(make_pair(nxtI, nxtJ));
		}
	}
	//A player will never pick up a ball twice.
	//If the ball is at (i, j), it can be assumed the nearest player came and picked it up.
	ans[s[0]][t[0]] = 0;
	pq.push(iii(0, ii(s[0], t[0])));
	//ans[i][j] includes the cost for nearest person to get to the ball.
	while (!pq.empty()) {
		iii tmp = pq.top(); pq.pop();
		int curI = tmp.se.fi, curJ = tmp.se.se;
//		cout << "CurI = " << curI << " curJ = " << curJ << "\n";
		if (tmp.fi != ans[curI][curJ]) continue;
		if (curI == s[n - 1] && curJ == t[n - 1]) {
			cout << tmp.fi - c * nearest[curI][curJ] << "\n";
			return 0;
		}
		int curCost = tmp.fi;
		fw (i, 0, 4) {
			fw (p, 1, max(w, h) + 1) {
				int nxtI = curI + p * dx[i], nxtJ = curJ + p * dy[i];
				int cost = a * p + b;
				if (!check(nxtI, nxtJ)) continue;
				if (curCost + cost + c * nearest[nxtI][nxtJ] < ans[nxtI][nxtJ]) {
					ans[nxtI][nxtJ] = curCost + cost + c * nearest[nxtI][nxtJ];
					pq.push(iii(ans[nxtI][nxtJ], ii(nxtI, nxtJ)));
				}
			}
			int nxtI = curI + dx[i], nxtJ = curJ + dy[i];
			if (!check(nxtI, nxtJ)) continue;
			if (curCost + c < ans[nxtI][nxtJ]) {
				ans[nxtI][nxtJ] = curCost + c;
				pq.push(iii(ans[nxtI][nxtJ], ii(nxtI, nxtJ)));
			}
		}
	}
	return 0;
}

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