Submission #1290512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290512		Gray	Soccer (JOI17_soccer)	C++20	0 / 100	3098 ms	118704 KiB

soccer

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = 2e18;
const ll MOD = 1000000007;
const ll N = 2e5;

long long facts[N*2+1];

void gen(){
    facts[0]=1;
    for (ll i=1; i<=N*2; i++){
        facts[i]=facts[i-1]*i%MOD;
    }
}
ll binpow(ll a, ll b){
    if (b==0) return 1;
    ll res=binpow(a, b/2);
    res=res*res%MOD;
    if (b&1) res=res*a%MOD;
    return res;
}
ll inv(ll x){
    return binpow(x, MOD-2);
}
ll binom(ll n, ll k){
    return facts[n]*inv(facts[n-k]*facts[k]%MOD)%MOD;
}

void solve(){
    ll h, w, A, B, C; 
    cin >> h >> w >> A >> B >> C;
    ll n; cin >> n;
    vector<array<ll, 2>> a(n);
    for (ll i=0; i<n; i++) cin >> a[i][0] >> a[i][1];

    queue<array<ll, 3>> que1;
    vector<vector<array<ll, 2>>> dist(h+1, vector<array<ll, 2>>(w+1, {-1, -1}));
    for (ll ind=0; ind<n; ind++) {
        ll i=a[ind][0], j=a[ind][1];
        dist[i][j]={ind, -1};
        que1.push({ind, i, j});
    }
    vector<pair<ll, ll>> mvs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    while (!que1.empty()){
        ll id, i, j; 
        id=que1.front()[0]; 
        i = que1.front()[1];
        j = que1.front()[2];
        que1.pop();
        for (auto [di, dj]:mvs){
            ll ni = i+di, nj=j+dj;
            if (ni>=0 and ni<=h and nj>=0 and nj<=w){
                if (dist[ni][nj][0]==-1){
                    dist[ni][nj][0]=id;
                    que1.push({id, ni, nj});
                }else if (dist[ni][nj][1]==-1 and dist[ni][nj][0]!=id){
                    dist[ni][nj][1]=id;
                    que1.push({id, ni, nj});
                }
            }
        }
    }
    // for (ll i=0; i<=h; i++){
    //     for (ll j=0; j<=w; j++) cout << dist[i][j][0] << ' ';
    //     cout << ln;
    // }
    // return;
    vector<vector<map<ll, ll>>> dp(h+1, vector<map<ll, ll>>(w+1));
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> que;
    que.push({0, a[0][0], a[0][1], 0});
    dp[a[0][0]][a[0][1]][0] = 0;
    vector<vector<map<ll, ll>>> vis(h+1, vector<map<ll, ll>>(w+1));
    while (!que.empty()){
        auto cur = que.top(); que.pop();
        ll i = cur[1], j=cur[2], cost = cur[0], usd=cur[3];
        if (vis[cur[1]][cur[2]].count(usd)) continue;
        vis[cur[1]][cur[2]][usd]=1;
        // cout << i << " " << j << ": " << cost << " through " << usd << ln;
        for (ll ni = 0; ni<=h; ni++){
            if (i==ni) continue;
            ll nj = j;
            if (usd==dist[ni][nj][0]){
                if (!dp[ni][nj].count(usd) or dp[ni][nj][usd]>cost+C*(abs(i-ni)+abs(j-nj))){
                    dp[ni][nj][usd]=cost+C*(abs(i-ni)+abs(j-nj)); 
                    que.push({cost+C*(abs(i-ni)+abs(j-nj)), ni, nj, usd});
                }
                ll susd = dist[ni][nj][1];
                if (!dp[ni][nj].count(susd) or dp[ni][nj][susd]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj][susd]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][susd], ni, nj, susd});
                }
            }else{
                ll susd = dist[ni][nj][0];
                if (!dp[ni][nj].count(susd) or dp[ni][nj][susd]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj][susd]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][susd], ni, nj, susd});
                }
            }
        }
        for (ll nj = 0; nj<=w; nj++){
            if (j==nj) continue;
            ll ni = i;
            if (usd==dist[ni][nj][0]){
                // cout << "H" << ni << "-" << nj << ln;
                if (!dp[ni][nj].count(usd) or dp[ni][nj][usd]>cost+C*(abs(i-ni)+abs(j-nj))){
                    dp[ni][nj][usd]=cost+C*(abs(i-ni)+abs(j-nj)); 
                    que.push({cost+C*(abs(i-ni)+abs(j-nj)), ni, nj, usd});
                }
                ll susd = dist[ni][nj][1];
                if (susd!=-1 and (!dp[ni][nj].count(susd) or dp[ni][nj][susd]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B)){
                    dp[ni][nj][susd]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][susd], ni, nj, susd});
                }
            }else{
                ll susd = dist[ni][nj][0];
                if (!dp[ni][nj].count(susd) or dp[ni][nj][susd]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj][susd]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][susd], ni, nj, susd});
                }
            }
        }
    }
    ll res=INF;
    // for (ll i=0; i<=h; i++){
    //     for (ll j=0; j<=w; j++){
    //         ll mn = INF;
    //         for (auto [x, y]:dp[i][j]) mn=min(mn, y);
    //         cout << mn << " ";
    //     }
    //     cout << ln;
    // }
    for (ll i=0; i<=h; i++){
        for (ll j=0; j<=w; j++){
            if (dp[i][j].count(n-1)){
                res=min(res, dp[i][j][n-1]);
            }
            ll mn = INF;
            for (auto [x, y]:dp[i][j]) mn=min(mn, y);
            res=min(res, mn+C*(abs(i-a[n-1][0])+abs(j-a[n-1][1])));
        }
    }
    cout << res << ln;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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