oj.uz

Submission #927027

# Submission time Handle Problem Language Result Execution time Memory
927027 2024-02-14T07:02:36 Z Gromp15 Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 19028 KB 
#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
	int h, w, a, b, c;
	cin >> h >> w >> a >> b >> c;
	int n; cin >> n;
	vector<ar<int, 2>> p(n);
	for (auto &x : p) cin >> x[0] >> x[1];
	// dp[x][y] = min cost to have a player at (x, y) possessing the ball
	// after a player gets the ball and moves and kicks the ball, they will not move again
	const int dx[]{0, 1, -1, 0}, dy[]{1, 0, 0, -1};
	auto in = [&](int x, int y) {
		return x >= 0 && y >= 0 && x <= h && y <= w;
	};
	vector<vector<int>> dp2(h+1, vector<int>(w+1, 1e9));
	{
		queue<ar<int, 2>> q;
		for (int i = 0; i < n; i++) {
			auto [x, y] = p[i];
			dp2[x][y] = 0;
			q.push({x, y});
		}
		while (q.size()) {
			auto [x, y] = q.front(); q.pop();
			for (int d = 0; d < 4; d++) {
				int nx = x + dx[d], ny = y + dy[d];
				if (!in(nx, ny)) continue;
				if (ckmin(dp2[nx][ny], dp2[x][y] + 1)) {
					q.push({nx, ny});
				}
			}
		}
	}
	const ll INF = 1e18;
	vector<vector<ll>> dp(h+1, vector<ll>(w+1, INF));
	dp[p[0][0]][p[0][1]] = 0;
	set<ar<ll, 3>> q;
	q.insert({0, p[0][0], p[0][1]});
	while (q.size()) {
		auto [weight, x, y] = *q.begin();
		q.erase(q.begin());
		// spread by walking
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d], ny = y + dy[d];
			ll new_cost = dp[x][y] + c;
			if (!in(nx, ny) || dp[nx][ny] <= new_cost) continue;
			if (dp[nx][ny] != INF) q.erase({dp[nx][ny], nx, ny});
			dp[nx][ny] = new_cost;
			q.insert({new_cost, nx, ny});
		}
		// spread by kicking and having someone pick it up
		for (int d = 0; d < 4; d++) {
			for (int use = 1; use <= max(h, w); use++) {
				int nx = x + dx[d] * use, ny = y + dy[d] * use;
				if (!in(nx, ny)) break;
				ll new_cost = dp[x][y] + (ll)dp2[nx][ny] * c + (ll)use * a + b;
				if (dp[nx][ny] <= new_cost) continue;
				if (dp[nx][ny] != INF) q.erase({dp[nx][ny], nx, ny});
				dp[nx][ny] = new_cost;
				q.insert({new_cost, nx, ny});
			}
		}
	}
	cout << dp[p[n-1][0]][p[n-1][1]] << '\n';



}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 3408 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1105 ms 12836 KB Output is correct
4 Correct 1539 ms 13908 KB Output is correct
5 Correct 257 ms 5500 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 17024 KB Output is correct
2 Correct 1174 ms 17544 KB Output is correct
3 Correct 783 ms 12972 KB Output is correct
4 Correct 1036 ms 11944 KB Output is correct
5 Correct 872 ms 12808 KB Output is correct
6 Correct 1127 ms 15708 KB Output is correct
7 Correct 1199 ms 18892 KB Output is correct
8 Correct 1116 ms 19024 KB Output is correct
9 Correct 1166 ms 18692 KB Output is correct
10 Correct 103 ms 3312 KB Output is correct
11 Correct 1174 ms 19028 KB Output is correct
12 Correct 1136 ms 18160 KB Output is correct
13 Correct 725 ms 13812 KB Output is correct
14 Correct 1213 ms 18864 KB Output is correct
15 Correct 905 ms 15148 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 3408 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1105 ms 12836 KB Output is correct
4 Correct 1539 ms 13908 KB Output is correct
5 Correct 257 ms 5500 KB Output is correct
6 Correct 1105 ms 17024 KB Output is correct
7 Correct 1174 ms 17544 KB Output is correct
8 Correct 783 ms 12972 KB Output is correct
9 Correct 1036 ms 11944 KB Output is correct
10 Correct 872 ms 12808 KB Output is correct
11 Correct 1127 ms 15708 KB Output is correct
12 Correct 1199 ms 18892 KB Output is correct
13 Correct 1116 ms 19024 KB Output is correct
14 Correct 1166 ms 18692 KB Output is correct
15 Correct 103 ms 3312 KB Output is correct
16 Correct 1174 ms 19028 KB Output is correct
17 Correct 1136 ms 18160 KB Output is correct
18 Correct 725 ms 13812 KB Output is correct
19 Correct 1213 ms 18864 KB Output is correct
20 Correct 905 ms 15148 KB Output is correct
21 Execution timed out 3052 ms 4748 KB Time limit exceeded
22 Halted 0 ms 0 KB -