oj.uz

Submission #753949

# Submission time Handle Problem Language Result Execution time Memory
753949 2023-06-06T11:28:54 Z pavement Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 135660 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//~ #define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

using lii = tuple<ll, int, int>;

int H, W, N, sS, sT, eS, eT, dr[] = {-1, 0, 0, 1}, dc[] = {0, -1, 1, 0}, dist[505][505];
ll A, B, C, ans[505][505];
queue<iii> Q;
priority_queue<lii, vector<lii>, greater<lii> > pq;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> H >> W >> A >> B >> C >> N;
	H++;
	W++;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			dist[i][j] = (int)1e9;
			ans[i][j] = (ll)1e16;
		}
	}
	for (int i = 1, S, T; i <= N; i++) {
		cin >> S >> T;
		S++;
		T++;
		dist[S][T] = 0;
		Q.emplace(0, S, T);
		if (i == 1) sS = S, sT = T;
		else if (i == N) eS = S, eT = T;
	}
	while (!Q.empty()) {
		auto [d, r, c] = Q.front();
		Q.pop();
		if (d != dist[r][c]) continue;
		for (int k = 0; k < 4; k++) {
			int nr = r + dr[k], nc = c + dc[k];
			if (1 <= nr && nr <= H && 1 <= nc && nc <= W && dist[nr][nc] > d + 1) {
				dist[nr][nc] = d + 1;
				Q.emplace(d + 1, nr, nc);
			}
		}
	}
	ans[sS][sT] = 0;
	pq.emplace(0, sS, sT);
	while (!pq.empty()) {
		auto [d, r, c] = pq.top();
		pq.pop();
		if (d != ans[r][c]) continue;
		for (int k = 1; k <= H; k++) {
			ll c1 = d + C * llabs(k - r);
			ll c2 = d + A * llabs(k - r) + B + C * dist[k][c];
			ll cur = min(c1, c2);
			if (ans[k][c] > cur) {
				ans[k][c] = cur;
				pq.emplace(ans[k][c], k, c);
			}
		}
		for (int k = 1; k <= W; k++) {
			ll c1 = d + C * llabs(k - c);
			ll c2 = d + A * llabs(k - c) + B + C * dist[r][k];
			ll cur = min(c1, c2);
			if (ans[r][k] > cur) {
				ans[r][k] = cur;
				pq.emplace(ans[r][k], r, k);
			}
		}
	}
	cout << ans[eS][eT] << '\n';
}

Compilation message

soccer.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 6336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1029 ms 11680 KB Output is correct
4 Correct 2557 ms 69096 KB Output is correct
5 Correct 233 ms 3576 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1299 ms 19880 KB Output is correct
2 Correct 1255 ms 11652 KB Output is correct
3 Correct 871 ms 11080 KB Output is correct
4 Correct 1054 ms 7504 KB Output is correct
5 Correct 944 ms 11684 KB Output is correct
6 Correct 1285 ms 7500 KB Output is correct
7 Correct 1202 ms 11720 KB Output is correct
8 Correct 1233 ms 11680 KB Output is correct
9 Correct 1112 ms 11784 KB Output is correct
10 Correct 106 ms 4428 KB Output is correct
11 Correct 1302 ms 11752 KB Output is correct
12 Correct 1214 ms 11584 KB Output is correct
13 Correct 736 ms 6860 KB Output is correct
14 Correct 1298 ms 11840 KB Output is correct
15 Correct 873 ms 11764 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 6336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1029 ms 11680 KB Output is correct
4 Correct 2557 ms 69096 KB Output is correct
5 Correct 233 ms 3576 KB Output is correct
6 Correct 1299 ms 19880 KB Output is correct
7 Correct 1255 ms 11652 KB Output is correct
8 Correct 871 ms 11080 KB Output is correct
9 Correct 1054 ms 7504 KB Output is correct
10 Correct 944 ms 11684 KB Output is correct
11 Correct 1285 ms 7500 KB Output is correct
12 Correct 1202 ms 11720 KB Output is correct
13 Correct 1233 ms 11680 KB Output is correct
14 Correct 1112 ms 11784 KB Output is correct
15 Correct 106 ms 4428 KB Output is correct
16 Correct 1302 ms 11752 KB Output is correct
17 Correct 1214 ms 11584 KB Output is correct
18 Correct 736 ms 6860 KB Output is correct
19 Correct 1298 ms 11840 KB Output is correct
20 Correct 873 ms 11764 KB Output is correct
21 Correct 238 ms 3288 KB Output is correct
22 Correct 1405 ms 19948 KB Output is correct
23 Correct 1321 ms 19532 KB Output is correct
24 Correct 1210 ms 11732 KB Output is correct
25 Correct 1484 ms 19888 KB Output is correct
26 Correct 1613 ms 19936 KB Output is correct
27 Correct 992 ms 8892 KB Output is correct
28 Correct 1467 ms 13188 KB Output is correct
29 Execution timed out 3058 ms 135660 KB Time limit exceeded
30 Halted 0 ms 0 KB -