Submission #1007584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007584		dimashhh	Soccer (JOI17_soccer)	C++17	35 / 100	3030 ms	21088 KiB

soccer

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 5e2 + 2, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n,m,d[N][N];
ll val[N][N];
ll a,b,c;
queue<pair<int,int>> q;
bool check(int x,int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
set<pair<ll,pair<int,int>>> st;
int fx,fy;
ll dist[N][N];
bool vis[N][N];
void test(){
    cin >> n >> m >> a >> b >> c;
    n++;
    m++;
    int f;cin >> f;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            d[i][j] = 1e9;
            dist[i][j] = 1e17;
        }
    }
    for(int i = 1;i <= f;i++) {
        int s,t;
        cin >> s >> t;
        s++;
        t++;
        if(i == 1){
            vis[s][t] = 1;
            dist[s][t] = 0;
            st.insert({0,{s,t}});
        }
        d[s][t] = 0;
        q.push({s,t});
        fx = s;fy = t;
    }
    while(!q.empty()){
        auto [x,y] = q.front();q.pop();
        val[x][y] = d[x][y] * c;
        for(int i = 0;i < 4;i++){
            int x1 = x + dx[i],y1 = y + dy[i];
            if(check(x1,y1) && d[x1][y1] > d[x][y] + 1){
                d[x1][y1] = d[x][y] +1;
                q.push({x1,y1});
            }
        }
    }
    while(!st.empty()){
        auto [d,t] = (*st.begin());
        st.erase(st.begin());
        int x = t.first,y = t.second;vis[x][y] = 1;
        for(int x1 = x + 1;x1 <= n;x1++) {
            if(vis[x1][y]) break;
            ll dd = min(abs(x - x1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x1][y] + abs(x1 - x) * a + (x1 != x ? b : 0));
            if (dd < dist[x1][y]) {
                st.erase({dist[x1][y], {x1, y}});
                dist[x1][y] = dd;
                st.insert({dist[x1][y], {x1, y}});
            }
        }
        for(int x1 = x - 1;x1 >= 1;x1--) {
            if(vis[x1][y]) break;
            ll dd = min(abs(x - x1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x1][y] + abs(x1 - x) * a + (x1 != x ? b : 0));
            if (dd < dist[x1][y]) {
                st.erase({dist[x1][y], {x1, y}});
                dist[x1][y] = dd;
                st.insert({dist[x1][y], {x1, y}});
            }
        }
        for(int y1 = 1;y1 <= m;y1++) {
            ll dd = min(abs(y - y1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x][y1] + abs(y - y1) * a + (y1 != y ? b : 0));
            if (dd < dist[x][y1]) {

                st.erase({dist[x][y1], {x, y1}});
                dist[x][y1] = dd;
                st.insert({dist[x][y1], {x, y1}});
            }
        }
    }
    cout << dist[fx][fy];
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

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