Submission #1294274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294274		fairkrash	Soccer (JOI17_soccer)	C++20	35 / 100	3093 ms	19744 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);
    ll h, w;
    cin >> h >> w;
    h++;
    w++;
    ll a, b, c;
    cin >> a >> b >> c;
    ll n;
    cin >> n;
    vector<pair<ll, ll>> 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;
    }
    {
        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()) {
            ll i = st.begin()->second / w;
            ll j = st.begin()->second % w;
            st.erase(st.begin());
            for (ll ij = max(j - 1, 0ll); ij <= min(j + 1, w - 1); 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 (ll ij = max(i - 1, 0ll); ij <= min(i + 1, h - 1); 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()) {
            ll i = st.begin()->second / w;
            ll j = st.begin()->second % w;
            if (i == s[n - 1].first && j == s[n - 1].second) {
                cout << dp[s[n - 1].first * w + s[n - 1].second] << endl;
                exit(0);
            }
            st.erase(st.begin());
            for (ll ij = max(j - 1, 0ll); ij <= min(j + 1, w - 1); 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 (ll 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});
                }
            }
            for (ll ij = max(i - 1, 0ll); ij <= min(i + 1, h - 1); ij++) {
                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});
                }
            }
            for (ll 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});
                }
            }
        }
    }
}

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