Submission #1000852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000852		Otalp	Soccer (JOI17_soccer)	C++14	100 / 100	466 ms	67412 KiB

soccer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

int ddp[600][600];
int dp[600][600][3];
int a[600][600];


void solve(){
    int n, m;
    cin>>n>>m;
    int A, B, C;
    cin>>A>>B>>C;
    int k;
    cin>>k;
    vector<pii> q;
    multiset<pair<int, pii> > ds;
    for(int i=1; i<=k; i++){
        int l, r;
        cin>>l>>r;
        q.pb({l, r});
        ds.insert({1, {l, r}});
    }
    vector<pii> nap = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    while(ds.size()){
        auto it = ds.begin();
        int x=it -> ss.ff, y = it -> ss.ss;
        if(ddp[x][y]){
            ds.erase(ds.begin());
            continue;
        }
        ddp[x][y] = it -> ff;
        ds.erase(it);
        for(pii h: nap){
            int l=x+h.ff, r=y+h.ss;
            if(l < 0 or l > n or r < 0 or r > m) continue;
            if(ddp[l][r]) continue;
            ds.insert({ddp[x][y] + 1, {l, r}});
        }
    }
    //for(int i=0; i<=n; i++){
    //    for(int j=0; j<=m; j++){
    //        cout<<ddp[i][j]<<' ';
    //    }
    //    cout<<'\n';
    //}
    multiset<pair<int, pair<pii, int>>> s;
    s.insert({1, {q[0], 0}});
    while(s.size()){
        auto it = s.begin();
        int x=it->ss.ff.ff, y=it->ss.ff.ss;
        int f=it->ss.ss;
        //cout<<x<<' '<<y<<' '<<f<<'\n';
        if(dp[x][y][f]){
            s.erase(it);
            continue;
        }
        dp[x][y][f] = it -> ff;
        s.erase(it);
        if(f == 1){
            if(!dp[x][y][0]) s.insert({dp[x][y][f], {{x, y}, 0}});
            for(int i=2; i<4; i++){
                int l=nap[i].ff + x, r=nap[i].ss + y;
                if(l < 0 or l > n or r < 0 or r > m) continue;
                if(dp[l][r][f]) continue;
                s.insert({dp[x][y][f] + A, {{l, r}, f}});
            }
        }
        if(f == 2){
            if(!dp[x][y][0]) s.insert({dp[x][y][f], {{x, y}, 0}});
            for(int i=0; i<2; i++){
                int l=nap[i].ff + x, r=nap[i].ss + y;
                if(l < 0 or l > n or r < 0 or r > m) continue;
                if(dp[l][r][f]) continue;
                s.insert({dp[x][y][f] + A, {{l, r}, f}});
            }
        }
        if(f == 0){
            if(!dp[x][y][1]) s.insert({dp[x][y][f] + (ddp[x][y] - 1) * C + B, {{x, y}, 1}});
            if(!dp[x][y][2]) s.insert({dp[x][y][f] + (ddp[x][y] - 1) * C + B, {{x, y}, 2}});
            for(int i=0; i<4; i++){
                int l=nap[i].ff + x, r=nap[i].ss + y;
                if(l < 0 or l > n or r < 0 or r > m) continue;
                if(dp[l][r][f]) continue;
                s.insert({dp[x][y][f] + C, {{l, r}, 0}}); 
            }
        }
    }
    int x=q[k-1].ff, y=q[k-1].ss;
    cout<<min(dp[x][y][0], min(dp[x][y][1], dp[x][y][2])) - 1<<'\n';
}


signed main(){
    solve();
}

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