Submission #1015404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015404		Baytoro	Soccer (JOI17_soccer)	C++17	100 / 100	713 ms	65340 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.ren
int dist[505][505][2][4];
int d[505][505];
vector<int> dx={1,-1,0,0},
            dy={0,0,1,-1};
int h,w;
bool check(int x, int y) {
    if(x<1) return 0;
    if(x>h) return 0;
    if(y<1) return 0;
    if(y>w) return 0;
    return 1;
}
void solve() {
    cin>>h>>w;h++,w++;
    int a,b,c;cin>>a>>b>>c;
    int n;cin>>n;
    vector<int> s(n),t(n);
    memset(dist,0x3f3f3f,sizeof dist);
    memset(d,0x3f3f3f,sizeof d);
    queue<pair<int,pair<int,int>>> pq;
    priority_queue<array<int,5>, vector<array<int,5>>, greater<array<int,5>>> dq;
    for(int i=0;i<n;i++) {
        cin>>s[i]>>t[i]; s[i]++,t[i]++;
        pq.push({0,{s[i],t[i]}});
        d[s[i]][t[i]]=0;
    }

    while(!pq.empty()) {
        int D=pq.front().fr,x=pq.front().sc.fr,y=pq.front().sc.sc;pq.pop();
        if(d[x][y]!=D) continue;
        for(int i=0;i<4;i++) {
            int X=x+dx[i],Y=y+dy[i];
            if(check(X,Y) && d[X][Y]>d[x][y]+1) {
                d[X][Y]=d[x][y]+1;
                pq.push({d[x][y]+1,{X,Y}});
            }
        }
    }
    for(int i=0;i<4;i++) {
        dq.push({0,i,1,s[0],t[0]});
        dist[s[0]][t[0]][1][i]=0;
    }
    /*for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) cout<<d[i][j]<<' ';
        cout<<endl;
    }*/
    while(!dq.empty()) {
        int D=dq.top()[0],dir=dq.top()[1],ball=dq.top()[2],x=dq.top()[3],y=dq.top()[4];

        dq.pop();

        if(dist[x][y][ball][dir]!=D) continue;
        //cout<<x<<' '<<y<<' '<<ball<<dir<<' '<<D<<endl;
        if(ball) {
            for(int i=0;i<4;i++) {
                int dd=D+c;
                if(check(x+dx[i],y+dy[i]) && dist[x+dx[i]][y+dy[i]][1][i]>dd) {
                    dist[x+dx[i]][y+dy[i]][1][i]=dd;
                    dq.push({dd,i,1,x+dx[i],y+dy[i]});
                }
                dd=D+a+b;
                if(check(x+dx[i],y+dy[i]) && dist[x+dx[i]][y+dy[i]][0][i]>dd) {
                    dist[x+dx[i]][y+dy[i]][0][i]=dd;
                    dq.push({dd,i,0,x+dx[i],y+dy[i]});
                }
            }
        }
        else {
            int X=x+dx[dir],Y=y+dy[dir];
            int dd=D+a;
            if(check(X,Y) && dist[X][Y][0][dir]>dd) {
                dist[X][Y][0][dir]=dd;
                dq.push({dd,dir,0,X,Y});
            }
            dd=D+d[x][y]*c;
            if(check(x,y) && dist[x][y][1][dir]>dd) {
                dist[x][y][1][dir]=dd;
                dq.push({dd,dir,1,x,y});
            }
        }
    }
    int ans=1e18;
    for(int i=0;i<4;i++) {
        ans=min(ans,dist[s[n-1]][t[n-1]][0][i]);
        ans=min(ans,dist[s[n-1]][t[n-1]][1][i]);
    }
    cout<<ans<<endl;



}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

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