제출 #1290497

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290497		Timosh	Soccer (JOI17_soccer)	C++20	0 / 100	1430 ms	327680 KiB

soccer

#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;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int int64_t
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vi vector<int>
#define vii vector<vi>
#define ld long double
#define pii pair<int, int>
mt19937 mt(time(0));

namespace io
{
    template <typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &pr)
    {
        cin >> pr.first >> pr.second;
        return cin;
    }

    template <typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &pr)
    {
        cout << pr.first << ' ' << pr.second;
        return cout;
    }

    template <typename T>
    istream &operator>>(istream &cin, vector<T> &vec)
    {
        for (T &i : vec)
            cin >> i;
        return cin;
    }

    template <typename T>
    ostream &operator<<(ostream &cout, vector<T> vec)
    {
        for (T i : vec)
            cout << i << ' ';
        return cout;
    }
}
using namespace io;
const int M = 998244353;
vi f(2e5 + 5);

int pw(int x, int y, int p = M)
{
    x %= p;
    int res = 1;
    while (y)
    {
        if (y & 1)
            res = res * x % p;
        x = x * x % p;
        y /= 2;
    }
    return res;
}

int inv(int a, int p = M) { return pw(a, p - 2, p); }
int C(int n, int k)
{
    if (k > n || k < 0)
        return 0;
    return f[n] * inv(f[n - k] * f[k]) % M;
}

void solve()
{
    int h, w, n, a, b, c;
    cin >> h >> w >> a >> b >> c >> n;
    vector<pii> v(n);
    cin >> v;
    vi d(n, 1e16);
    d[0] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 0});
    while (!pq.empty())
    {
        pii x = pq.top();
        pq.pop();
        if (d[x.second] < x.first)
            continue;
        d[x.second] = x.first;
        for (int i = 0; i < n; i++)
        {
            int dx = abs(v[i].first - v[x.second].first);
            int dy = abs(v[i].second - v[x.second].second);
            int y = x.first + min((dx + dy) * c, b + min(dx, dy) * c);
            if (y >= d[i])
                continue;
            pq.push({y, i});
        }
    }
    cout << d[n - 1];
}

signed main()
{
    f[0] = 1;
    for (int i = 1; i <= 2e5; i++)
        f[i] = f[i - 1] * i % M;
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve(), cout << '\n';
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65