oj.uz

Submission #141071

# Submission time Handle Problem Language Result Execution time Memory
141071 2019-08-06T13:46:43 Z DrumpfTheGodEmperor Soccer (JOI17_soccer) C++14
35 / 100
 2170 ms 262144 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6004 KB Output is correct
2 Correct 7 ms 4920 KB Output is correct
3 Correct 245 ms 10768 KB Output is correct
4 Correct 64 ms 7536 KB Output is correct
5 Correct 421 ms 7664 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7680 KB Output is correct
2 Correct 22 ms 6048 KB Output is correct
3 Correct 318 ms 10716 KB Output is correct
4 Correct 2170 ms 10612 KB Output is correct
5 Correct 380 ms 10772 KB Output is correct
6 Correct 662 ms 10732 KB Output is correct
7 Correct 41 ms 10884 KB Output is correct
8 Correct 50 ms 10788 KB Output is correct
9 Correct 33 ms 7808 KB Output is correct
10 Correct 51 ms 6164 KB Output is correct
11 Correct 90 ms 10916 KB Output is correct
12 Correct 174 ms 10772 KB Output is correct
13 Correct 455 ms 10732 KB Output is correct
14 Correct 37 ms 10784 KB Output is correct
15 Correct 17 ms 6192 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6004 KB Output is correct
2 Correct 7 ms 4920 KB Output is correct
3 Correct 245 ms 10768 KB Output is correct
4 Correct 64 ms 7536 KB Output is correct
5 Correct 421 ms 7664 KB Output is correct
6 Correct 42 ms 7680 KB Output is correct
7 Correct 22 ms 6048 KB Output is correct
8 Correct 318 ms 10716 KB Output is correct
9 Correct 2170 ms 10612 KB Output is correct
10 Correct 380 ms 10772 KB Output is correct
11 Correct 662 ms 10732 KB Output is correct
12 Correct 41 ms 10884 KB Output is correct
13 Correct 50 ms 10788 KB Output is correct
14 Correct 33 ms 7808 KB Output is correct
15 Correct 51 ms 6164 KB Output is correct
16 Correct 90 ms 10916 KB Output is correct
17 Correct 174 ms 10772 KB Output is correct
18 Correct 455 ms 10732 KB Output is correct
19 Correct 37 ms 10784 KB Output is correct
20 Correct 17 ms 6192 KB Output is correct
21 Correct 717 ms 201576 KB Output is correct
22 Correct 1063 ms 16880 KB Output is correct
23 Correct 1322 ms 29244 KB Output is correct
24 Correct 868 ms 17180 KB Output is correct
25 Correct 749 ms 10768 KB Output is correct
26 Correct 1326 ms 17308 KB Output is correct
27 Runtime error 1670 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -