Submission #1166693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166693		mertbbm	Soccer (JOI17_soccer)	C++20	100 / 100	349 ms	22588 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

void solve(){
	int h,w;
	cin >> h >> w;
	h++; w++;
	int a,b,c;
	cin >> a >> b >> c;
	
	int n;
	cin >> n;
	pii arr[n];
	
	int32_t dist[h][w];
	memset(dist,-1,sizeof(dist));
	queue<pii>q;
	
	pii dir[4]={
		{1,0},
		{-1,0},
		{0,1},
		{0,-1},
	};
	
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
		dist[arr[x].first][arr[x].second]=0;
		q.push({arr[x].first,arr[x].second});
	}
	
	while(!q.empty()){
		pii cur=q.front();
		q.pop();
		for(auto it:dir){
			int nx=it.first+cur.first;
			int ny=it.second+cur.second;
			if(nx<0||ny<0||nx>=h||ny>=w) continue;
			if(dist[nx][ny]!=-1) continue;
			dist[nx][ny]=dist[cur.first][cur.second]+1;
			q.push({nx,ny});
		}
	}

	int dist2[5][h][w];
	memset(dist2,-1,sizeof(dist2));
	priority_queue<pair<int,array<int,3>>,vector<pair<int,array<int,3>>>,greater<pair<int,array<int,3>>>>pq;
	
	dist2[0][arr[0].first][arr[0].second]=0;
	pq.push({0,{0,arr[0].first,arr[0].second}});
	
	while(!pq.empty()){
		pair<int,array<int,3>>cur=pq.top();
		pq.pop();
		int x=cur.second[1];
		int y=cur.second[2];
		int k=cur.second[0];
		int d=cur.first;
		//cout << x << " " << y << " " << k << " " << d << "\n";
		
		if(dist2[k][x][y]!=d) continue;
		
		if(k==0){
			////move with the ball
			for(auto it:dir){
				int nx=it.first+x;
				int ny=it.second+y;
				int nd=d+c;
				if(nx<0||ny<0||nx>=h||ny>=w) continue;
				if(dist2[0][nx][ny]!=-1&&dist2[0][nx][ny]<=nd) continue;
				dist2[0][nx][ny]=nd;
				pq.push({nd,{0,nx,ny}});
			}
			
			//move up
			for(int i=1;i<=4;i++){
				int nd=d+b;
				if(dist2[i][x][y]!=-1&&dist2[i][x][y]<=nd) continue;
				dist2[i][x][y]=nd;
				pq.push({nd,{i,x,y}});
			}
		}
		else{
			//move down
			if(dist2[0][x][y]==-1||dist2[0][x][y]>d+dist[x][y]*c){
				dist2[0][x][y]=d+dist[x][y]*c;
				pq.push({d+dist[x][y]*c,{0,x,y}});
			}
			
			//move
			int nx=x;
			int ny=y;
			if(k==1) nx++;
			if(k==2) nx--;
			if(k==3) ny++;
			if(k==4) ny--;
			if(nx<0||ny<0||nx>=h||ny>=w) continue;
			int nd=d+a;
			if(dist2[k][nx][ny]!=-1&&dist2[k][nx][ny]<=nd) continue;
			dist2[k][nx][ny]=nd;
			pq.push({nd,{k,nx,ny}});
		}
		
		//for(int i=0;i<h;i++){
			//for(int j=0;j<w;j++){
				//cout << dist2[0][i][j] << " ";
			//}
			//cout << "\n";
		//}
		//cout << "\n";
	}
	
	cout << dist2[0][arr[n-1].first][arr[n-1].second];
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("in.txt","w",stdout);
	int t=1;
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

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