# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1038584 |
2024-07-30T02:27:05 Z |
juicy |
Soccer (JOI17_soccer) |
C++17 |
|
266 ms |
19908 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 505, mxN = 1e5 + 5;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int n, m, k, A, B, C;
int s[mxN], t[mxN], f[N][N];
long long d[N][N][5];
bool inside(int i, int j) {
return 0 <= i && i <= n && 0 <= j && j <= m;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> A >> B >> C >> k;
memset(f, -1, sizeof(f));
queue<array<int, 2>> q;
for (int i = 1; i <= k; ++i) {
cin >> s[i] >> t[i];
f[s[i]][t[i]] = 0;
q.push({s[i], t[i]});
}
while (q.size()) {
auto [u, v] = q.front(); q.pop();
for (int dr = 0; dr < 4; ++dr) {
int x = u + dx[dr], y = v + dy[dr];
if (inside(x, y) && f[x][y] == -1) {
f[x][y] = f[u][v] + 1;
q.push({x, y});
}
}
}
memset(d, 0x3f, sizeof(d));
using T = tuple<long long, int, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
auto psh = [&](int i, int j, int t, long long w) {
if (inside(i, j) && d[i][j][t] > w) {
pq.push({d[i][j][t] = w, i, j, t});
}
};
psh(s[1], t[1], 4, 0);
while (pq.size()) {
auto [c, x, y, t] = pq.top(); pq.pop();
if (c != d[x][y][t]) {
continue;
}
if (t == 4) {
for (int dr = 0; dr < 4; ++dr) {
int i = x + dx[dr], j = y + dy[dr];
psh(i, j, dr, c + B + A);
psh(i, j, 4, c + C);
}
} else {
psh(x + dx[t], y + dy[t], t, c + A);
psh(x, y, 4, c + (long long) f[x][y] * C);
}
}
cout << d[s[k]][t[k]][4];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
12936 KB |
Output is correct |
2 |
Correct |
4 ms |
11356 KB |
Output is correct |
3 |
Correct |
214 ms |
17600 KB |
Output is correct |
4 |
Correct |
235 ms |
17680 KB |
Output is correct |
5 |
Correct |
58 ms |
11612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
17600 KB |
Output is correct |
2 |
Correct |
216 ms |
17708 KB |
Output is correct |
3 |
Correct |
185 ms |
17576 KB |
Output is correct |
4 |
Correct |
165 ms |
17604 KB |
Output is correct |
5 |
Correct |
172 ms |
17612 KB |
Output is correct |
6 |
Correct |
199 ms |
17596 KB |
Output is correct |
7 |
Correct |
189 ms |
17916 KB |
Output is correct |
8 |
Correct |
195 ms |
17632 KB |
Output is correct |
9 |
Correct |
193 ms |
17664 KB |
Output is correct |
10 |
Correct |
37 ms |
13032 KB |
Output is correct |
11 |
Correct |
194 ms |
17652 KB |
Output is correct |
12 |
Correct |
192 ms |
17624 KB |
Output is correct |
13 |
Correct |
135 ms |
17608 KB |
Output is correct |
14 |
Correct |
185 ms |
17648 KB |
Output is correct |
15 |
Correct |
160 ms |
17660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
12936 KB |
Output is correct |
2 |
Correct |
4 ms |
11356 KB |
Output is correct |
3 |
Correct |
214 ms |
17600 KB |
Output is correct |
4 |
Correct |
235 ms |
17680 KB |
Output is correct |
5 |
Correct |
58 ms |
11612 KB |
Output is correct |
6 |
Correct |
231 ms |
17600 KB |
Output is correct |
7 |
Correct |
216 ms |
17708 KB |
Output is correct |
8 |
Correct |
185 ms |
17576 KB |
Output is correct |
9 |
Correct |
165 ms |
17604 KB |
Output is correct |
10 |
Correct |
172 ms |
17612 KB |
Output is correct |
11 |
Correct |
199 ms |
17596 KB |
Output is correct |
12 |
Correct |
189 ms |
17916 KB |
Output is correct |
13 |
Correct |
195 ms |
17632 KB |
Output is correct |
14 |
Correct |
193 ms |
17664 KB |
Output is correct |
15 |
Correct |
37 ms |
13032 KB |
Output is correct |
16 |
Correct |
194 ms |
17652 KB |
Output is correct |
17 |
Correct |
192 ms |
17624 KB |
Output is correct |
18 |
Correct |
135 ms |
17608 KB |
Output is correct |
19 |
Correct |
185 ms |
17648 KB |
Output is correct |
20 |
Correct |
160 ms |
17660 KB |
Output is correct |
21 |
Correct |
65 ms |
12380 KB |
Output is correct |
22 |
Correct |
258 ms |
17608 KB |
Output is correct |
23 |
Correct |
250 ms |
14804 KB |
Output is correct |
24 |
Correct |
265 ms |
14712 KB |
Output is correct |
25 |
Correct |
220 ms |
17608 KB |
Output is correct |
26 |
Correct |
264 ms |
17916 KB |
Output is correct |
27 |
Correct |
141 ms |
13284 KB |
Output is correct |
28 |
Correct |
165 ms |
13764 KB |
Output is correct |
29 |
Correct |
249 ms |
16688 KB |
Output is correct |
30 |
Correct |
166 ms |
13652 KB |
Output is correct |
31 |
Correct |
194 ms |
17648 KB |
Output is correct |
32 |
Correct |
262 ms |
19908 KB |
Output is correct |
33 |
Correct |
182 ms |
17736 KB |
Output is correct |
34 |
Correct |
266 ms |
17656 KB |
Output is correct |
35 |
Correct |
150 ms |
13824 KB |
Output is correct |