Submission #1166683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166683		mertbbm	Soccer (JOI17_soccer)	C++20	35 / 100	1336 ms	327680 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];
	
	int 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[h][w];
	memset(dist2,-1,sizeof(dist2));
	priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>pq;
	
	dist2[arr[0].first][arr[0].second]=0;
	pq.push({0,{arr[0]}});
	
	while(!pq.empty()){
		pair<int,pii>cur=pq.top();
		pq.pop();
		int x=cur.second.first;
		int y=cur.second.second;
		int d=cur.first;
		
		if(dist2[x][y]!=d) continue;
		
		//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[nx][ny]!=-1&&dist2[nx][ny]<=nd) continue;
			dist2[nx][ny]=nd;
			pq.push({nd,{nx,ny}});
		}
		
		//throw it then catch it back
		for(int i=0;i<h;i++){
			if(i==x) continue;
			int diff=abs(i-x);
			int nd=d+dist[i][y]*c+b+diff*a;
			if(dist2[i][y]!=-1&&dist2[i][y]<=nd) continue;
			dist2[i][y]=nd;
			pq.push({nd,{i,y}});
		}
		
		for(int i=0;i<w;i++){
			if(i==y) continue;
			int diff=abs(i-y);
			int nd=d+dist[x][i]*c+b+diff*a;
			if(dist2[x][i]!=-1&&dist2[x][i]<=nd) continue;
			dist2[x][i]=nd;
			pq.push({nd,{x,i}});
		}
	}
	
	cout << dist2[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: 0 / 65