| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 234018 | 2020-05-22T20:03:35 Z | dolphingarlic | Soccer (JOI17_soccer) | C++14 | 622 ms | 23920 KB |
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;using namespace std;struct P {int x, y, d;ll f;};bool operator<(P A, P B) { return A.f > B.f; }int h, w;ll v[501][501], t[501][501], d[501][501][6];bool vis[501][501][6];int dx[6]{0, 0, 0, 0, 1, -1}, dy[6]{0, 0, 1, -1, 0, 0};bool ins(int x, int y) { return (~x && ~y && x <= h && y <= w); }int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n;ll a, b, c;P dest;priority_queue<P> pq;cin >> h >> w >> a >> b >> c >> n;memset(v, 0x3f, sizeof(v));memset(t, 0x3f, sizeof(t));memset(d, 0x3f, sizeof(d));FOR(i, 0, n) {int x, y;cin >> x >> y;v[x][y] = 0;if (!i) pq.push({x, y, 1, 0}), d[x][y][1] = 0;if (i == n - 1) dest = {x, y, 0, 0};}FOR(i, 1, h + 1) FOR(j, 0, w + 1) {v[i][j] = min(v[i][j], v[i - 1][j] + 1);v[h - i][j] = min(v[h - i][j], v[h - i + 1][j] + 1);}FOR(i, 0, h + 1) FOR(j, 0, w + 1) FOR(k, 0, w + 1) {t[i][j] = min(t[i][j], v[i][k] + abs(j - k));}while (pq.size()) {P curr = pq.top();pq.pop();if (!vis[curr.x][curr.y][curr.d]) {vis[curr.x][curr.y][curr.d] = true;if (!curr.d) {if (curr.f + t[curr.x][curr.y] * c < d[curr.x][curr.y][1]) {d[curr.x][curr.y][1] = curr.f + t[curr.x][curr.y] * c;pq.push({curr.x, curr.y, 1, curr.f + t[curr.x][curr.y] * c});}} else if (curr.d == 1) {FOR(i, 2, 6) {int nx = curr.x + dx[i], ny = curr.y + dy[i];if (ins(nx, ny) && curr.f + c < d[nx][ny][1]) {d[nx][ny][1] = curr.f + c;pq.push({nx, ny, 1, curr.f + c});}if (curr.f + b < d[curr.x][curr.y][i]) {d[curr.x][curr.y][i] = curr.f + b;pq.push({curr.x, curr.y, i, curr.f + b});}}} else {int nx = curr.x + dx[curr.d], ny = curr.y + dy[curr.d];if (ins(nx, ny) && curr.f + a < d[nx][ny][curr.d]) {d[nx][ny][curr.d] = curr.f + a;pq.push({nx, ny, curr.d, curr.f + a});}if (curr.f < d[curr.x][curr.y][0]) {d[curr.x][curr.y][0] = curr.f;pq.push({curr.x, curr.y, 0, curr.f});}}}}ll ans = LLONG_MAX;FOR(i, 0, 6) ans = min(ans, d[dest.x][dest.y][i]);cout << ans;return 0;}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 100 ms | 18672 KB | Output is correct |
| 2 | Correct | 13 ms | 16128 KB | Output is correct |
| 3 | Correct | 464 ms | 23892 KB | Output is correct |
| 4 | Correct | 477 ms | 23776 KB | Output is correct |
| 5 | Correct | 99 ms | 17144 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 485 ms | 23780 KB | Output is correct |
| 2 | Correct | 482 ms | 23908 KB | Output is correct |
| 3 | Correct | 378 ms | 23520 KB | Output is correct |
| 4 | Correct | 424 ms | 23904 KB | Output is correct |
| 5 | Correct | 354 ms | 23912 KB | Output is correct |
| 6 | Correct | 446 ms | 23776 KB | Output is correct |
| 7 | Correct | 493 ms | 23908 KB | Output is correct |
| 8 | Correct | 480 ms | 23780 KB | Output is correct |
| 9 | Correct | 525 ms | 23780 KB | Output is correct |
| 10 | Correct | 60 ms | 19192 KB | Output is correct |
| 11 | Correct | 488 ms | 23780 KB | Output is correct |
| 12 | Correct | 492 ms | 23780 KB | Output is correct |
| 13 | Correct | 341 ms | 23528 KB | Output is correct |
| 14 | Correct | 486 ms | 23908 KB | Output is correct |
| 15 | Correct | 359 ms | 23908 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 100 ms | 18672 KB | Output is correct |
| 2 | Correct | 13 ms | 16128 KB | Output is correct |
| 3 | Correct | 464 ms | 23892 KB | Output is correct |
| 4 | Correct | 477 ms | 23776 KB | Output is correct |
| 5 | Correct | 99 ms | 17144 KB | Output is correct |
| 6 | Correct | 485 ms | 23780 KB | Output is correct |
| 7 | Correct | 482 ms | 23908 KB | Output is correct |
| 8 | Correct | 378 ms | 23520 KB | Output is correct |
| 9 | Correct | 424 ms | 23904 KB | Output is correct |
| 10 | Correct | 354 ms | 23912 KB | Output is correct |
| 11 | Correct | 446 ms | 23776 KB | Output is correct |
| 12 | Correct | 493 ms | 23908 KB | Output is correct |
| 13 | Correct | 480 ms | 23780 KB | Output is correct |
| 14 | Correct | 525 ms | 23780 KB | Output is correct |
| 15 | Correct | 60 ms | 19192 KB | Output is correct |
| 16 | Correct | 488 ms | 23780 KB | Output is correct |
| 17 | Correct | 492 ms | 23780 KB | Output is correct |
| 18 | Correct | 341 ms | 23528 KB | Output is correct |
| 19 | Correct | 486 ms | 23908 KB | Output is correct |
| 20 | Correct | 359 ms | 23908 KB | Output is correct |
| 21 | Correct | 120 ms | 17384 KB | Output is correct |
| 22 | Correct | 588 ms | 23920 KB | Output is correct |
| 23 | Correct | 537 ms | 20580 KB | Output is correct |
| 24 | Correct | 615 ms | 20716 KB | Output is correct |
| 25 | Correct | 555 ms | 23780 KB | Output is correct |
| 26 | Correct | 563 ms | 23780 KB | Output is correct |
| 27 | Correct | 405 ms | 17848 KB | Output is correct |
| 28 | Correct | 390 ms | 17784 KB | Output is correct |
| 29 | Correct | 525 ms | 20580 KB | Output is correct |
| 30 | Correct | 373 ms | 17656 KB | Output is correct |
| 31 | Correct | 539 ms | 23904 KB | Output is correct |
| 32 | Correct | 622 ms | 23776 KB | Output is correct |
| 33 | Correct | 471 ms | 23780 KB | Output is correct |
| 34 | Correct | 615 ms | 23904 KB | Output is correct |
| 35 | Correct | 331 ms | 17640 KB | Output is correct |