Submission #1007662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007662		dimashhh	Soccer (JOI17_soccer)	C++17	35 / 100	3036 ms	20928 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];
set<int> R[N],C[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){
            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});
            }
        }
    }
    for(int i = 1;i <= n;i++){
        R[i].insert(-m);
        R[i].insert(m + m);
    }
    for(int i = 1;i <= m;i++){
        C[i].insert(-n);
        C[i].insert(n + n);
    }
    while(!st.empty()){
        auto [d,t] = (*st.begin());
        st.erase(st.begin());
        int x = t.first,y = t.second;
        for(int dir =0 ;dir < 4;dir++){
            int nx = x +dx[dir],ny = y + dy[dir];
            ll du = d + c;
            if(check(nx,ny) && dist[nx][ny] > du){
                st.erase({dist[nx][ny],{nx,ny}});
                dist[nx][ny] = du;
                st.insert({dist[nx][ny],{nx,ny}});
            }
        }
        for(int x1 = 1;x1 <= n;x1++){
            ll dd = dist[x][y] + val[x1][y] + abs(x1 - x) * a + b;
            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 = dist[x][y] + val[x][y1] + abs(y1 - y) * a + b;
            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