Submission #1294338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294338		fairkrash	Soccer (JOI17_soccer)	C++20	35 / 100	3094 ms	19656 KiB

soccer

#include <bits/stdc++.h>
#include <random>

using namespace std;
using ll = long long;
using ld = long double;

ll INF = 1e18;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int h, w;
    cin >> h >> w;
    h++;
    w++;
    ll a, b, c;
    cin >> a >> b >> c;
    int n;
    cin >> n;
    vector<pair<int, int>> s(n);
    for (ll i = 0; i < n; i++) {
        cin >> s[i].first >> s[i].second;
    }
    vector<ll> pref((h) * (w), INF);
    for (ll i = 0; i < n; i++) {
        pref[s[i].first * w + s[i].second] = 0;
    }
    if (c <= a) {
        cout << (abs(s[0].first - s[n - 1].first) + abs(s[0].second - s[n - 1].second)) * c;
        return 0;
    }
    {
        set<pair<ll, ll>> st;
        for (ll i = 0; i < n; i++) {
            st.insert({0, s[i].first * w + s[i].second});
        }
        while (!st.empty()) {
            int i = st.begin()->second / w;
            int j = st.begin()->second % w;
            st.erase(st.begin());
            for (int ij = max(0, j - 1); ij < min(j + 2, w); ij++) {
                if (pref[i * w + ij] > pref[i * w + j] + abs(ij - j) * c) {
                    st.erase({pref[i * w + ij], i * w + ij});
                    pref[i * w + ij] = pref[i * w + j] + abs(ij - j) * c;
                    st.insert({pref[i * w + ij], i * w + ij});
                }
            }
            for (int ij = max(0, i - 1); ij < min(i + 2, h); ij++) {
                if (pref[ij * w + j] > pref[i * w + j] + abs(ij - i) * c) {
                    st.erase({pref[ij * w + j], ij * w + j});
                    pref[ij * w + j] = pref[i * w + j] + abs(i - ij) * c;
                    st.insert({pref[ij * w + j], ij * w + j});
                }
            }
        }
    }
    {
        vector<ll> dp((h) * (w), INF);
        dp[s[0].first * w + s[0].second] = 0;
        set<pair<ll, ll>> st;
        st.insert({0, s[0].first * w + s[0].second});
        while (!st.empty()) {
            int i = st.begin()->second / w;
            int j = st.begin()->second % w;
            if (dp[s[n - 1].first * w + s[n - 1].second] <= c + st.begin()->first &&
                dp[s[n - 1].first * w + s[n - 1].second] <= a + b + st.begin()->first) {
                cout << dp[s[n - 1].first * w + s[n - 1].second] << endl;
                exit(0);
            }
            st.erase(st.begin());
            for (int ij = 0; ij < w; ij++) {
                if (dp[i * w + ij] > dp[i * w + j] + abs(ij - j) * a + b + pref[i * w + ij]) {
                    st.erase({dp[i * w + ij], i * w + ij});
                    dp[i * w + ij] = dp[i * w + j] + abs(ij - j) * a + b + pref[i * w + ij];
                    st.insert({dp[i * w + ij], i * w + ij});
                }
                if (dp[i * w + ij] > dp[i * w + j] + abs(ij - j) * c) {
                    st.erase({dp[i * w + ij], i * w + ij});
                    dp[i * w + ij] = dp[i * w + j] + abs(ij - j) * c;
                    st.insert({dp[i * w + ij], i * w + ij});
                }
            }
            for (int ij = 0; ij < h; ij++) {
                if (dp[ij * w + j] > dp[i * w + j] + abs(ij - i) * a + b + pref[ij * w + j]) {
                    st.erase({dp[ij * w + j], ij * w + j});
                    dp[ij * w + j] = dp[i * w + j] + abs(i - ij) * a + b + pref[ij * w + j];
                    st.insert({dp[ij * w + j], ij * w + j});
                }
                if (dp[ij * w + j] > dp[i * w + j] + abs(ij - i) * c) {
                    st.erase({dp[ij * w + j], ij * w + j});
                    dp[ij * w + j] = dp[i * w + j] + abs(i - ij) * c;
                    st.insert({dp[ij * w + j], ij * w + j});
                }
            }
        }
        cout << dp[s[n - 1].first * w + s[n - 1].second] << endl;
    }
}

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