oj.uz

Submission #1051962

# Submission time Handle Problem Language Result Execution time Memory
1051962 2024-08-10T10:49:18 Z SamAnd Soccer (JOI17_soccer) C++17
5 / 100
 1471 ms 28588 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], y[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 66 ms 4240 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 362 ms 15552 KB Output is correct
4 Correct 136 ms 4800 KB Output is correct
5 Correct 278 ms 13936 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 5980 KB Output is correct
2 Correct 74 ms 3480 KB Output is correct
3 Correct 416 ms 15544 KB Output is correct
4 Correct 1471 ms 28588 KB Output is correct
5 Correct 441 ms 15028 KB Output is correct
6 Incorrect 310 ms 10176 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4240 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 362 ms 15552 KB Output is correct
4 Correct 136 ms 4800 KB Output is correct
5 Correct 278 ms 13936 KB Output is correct
6 Correct 132 ms 5980 KB Output is correct
7 Correct 74 ms 3480 KB Output is correct
8 Correct 416 ms 15544 KB Output is correct
9 Correct 1471 ms 28588 KB Output is correct
10 Correct 441 ms 15028 KB Output is correct
11 Incorrect 310 ms 10176 KB Output isn't correct
12 Halted 0 ms 0 KB -