oj.uz

Submission #1051969

# Submission time Handle Problem Language Result Execution time Memory
1051969 2024-08-10T10:50:25 Z SamAnd Soccer (JOI17_soccer) C++17
35 / 100
 1606 ms 28816 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 503;
const int xx[4] = {0, 1, 0, -1};
const int yy[4] = {1, 0, -1, 0};

int n, m;
int A, B, C;
int k;
int x[N * N], y[N * N];
bool cc[N][N];

struct ban
{
    int x, y, z;
    ll d;
    ban(){}
    ban(int x, int y, int z, ll d)
    {
        this->x = x;
        this->y = y;
        this->z = z;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

bool c[N][N][4 + 1];

void solv()
{
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> k;
    for (int i = 1; i <= k; ++i)
    {
        cin >> x[i] >> y[i];
        cc[x[i]][y[i]] = true;
    }

    priority_queue<ban> q;
    q.push(ban(x[1], y[1], 4, 0));
    while (!q.empty())
    {
        ban t = q.top();
        q.pop();
        if (c[t.x][t.y][t.z])
            continue;
        c[t.x][t.y][t.z] = true;
        if (t.x == x[k] && t.y == y[k])
        {
            cout << t.d << "\n";
            return;
        }
        int minu = N;
        for (int i = 0; i < 4; ++i)
        {
            int x = t.x;
            int y = t.y;
            while (1)
            {
                if (!(0 <= x && x <= n && 0 <= y && y <= m))
                    break;
                if (cc[x][y])
                {
                    minu = min(minu, abs(x - t.x) + abs(y - t.y));
                    break;
                }
                x += xx[i];
                y += yy[i];
            }
        }
        q.push(ban(t.x, t.y, 4, t.d + minu * 1LL * C));

        if (t.z < 4)
        {
            ban h = t;
            h.x += xx[t.z];
            h.y += yy[t.z];
            h.d += A;
            if (0 <= h.x && h.x <= n && 0 <= h.y && h.y <= m)
                q.push(h);
        }
        else
        {
            for (int i = 0; i < 4; ++i)
            {
                ban h = t;
                h.x += xx[i];
                h.y += yy[i];
                h.d += C;
                if (0 <= h.x && h.x <= n && 0 <= h.y && h.y <= m)
                    q.push(h);
            }
            for (int i = 0; i < 4; ++i)
            {
                ban h = t;
                h.d += B;
                h.z = i;
                q.push(h);
            }
        }
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5852 KB Output is correct
2 Correct 1 ms 2548 KB Output is correct
3 Correct 294 ms 16072 KB Output is correct
4 Correct 117 ms 5828 KB Output is correct
5 Correct 316 ms 15380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 6600 KB Output is correct
2 Correct 75 ms 4296 KB Output is correct
3 Correct 513 ms 16188 KB Output is correct
4 Correct 1606 ms 28588 KB Output is correct
5 Correct 396 ms 15288 KB Output is correct
6 Correct 627 ms 16276 KB Output is correct
7 Correct 212 ms 16808 KB Output is correct
8 Correct 253 ms 15672 KB Output is correct
9 Correct 29 ms 4304 KB Output is correct
10 Correct 19 ms 5840 KB Output is correct
11 Correct 531 ms 28816 KB Output is correct
12 Correct 713 ms 27488 KB Output is correct
13 Correct 420 ms 16564 KB Output is correct
14 Correct 170 ms 16308 KB Output is correct
15 Correct 16 ms 3444 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5852 KB Output is correct
2 Correct 1 ms 2548 KB Output is correct
3 Correct 294 ms 16072 KB Output is correct
4 Correct 117 ms 5828 KB Output is correct
5 Correct 316 ms 15380 KB Output is correct
6 Correct 200 ms 6600 KB Output is correct
7 Correct 75 ms 4296 KB Output is correct
8 Correct 513 ms 16188 KB Output is correct
9 Correct 1606 ms 28588 KB Output is correct
10 Correct 396 ms 15288 KB Output is correct
11 Correct 627 ms 16276 KB Output is correct
12 Correct 212 ms 16808 KB Output is correct
13 Correct 253 ms 15672 KB Output is correct
14 Correct 29 ms 4304 KB Output is correct
15 Correct 19 ms 5840 KB Output is correct
16 Correct 531 ms 28816 KB Output is correct
17 Correct 713 ms 27488 KB Output is correct
18 Correct 420 ms 16564 KB Output is correct
19 Correct 170 ms 16308 KB Output is correct
20 Correct 16 ms 3444 KB Output is correct
21 Correct 99 ms 8948 KB Output is correct
22 Correct 751 ms 28332 KB Output is correct
23 Correct 933 ms 28080 KB Output is correct
24 Correct 425 ms 28096 KB Output is correct
25 Correct 610 ms 15800 KB Output is correct
26 Correct 583 ms 15288 KB Output is correct
27 Correct 165 ms 3660 KB Output is correct
28 Correct 287 ms 4172 KB Output is correct
29 Correct 842 ms 16568 KB Output is correct
30 Correct 377 ms 7364 KB Output is correct
31 Correct 116 ms 9660 KB Output is correct
32 Correct 166 ms 16312 KB Output is correct
33 Correct 668 ms 15924 KB Output is correct
34 Incorrect 55 ms 5824 KB Output isn't correct
35 Halted 0 ms 0 KB -