oj.uz

Submission #33338

# Submission time Handle Problem Language Result Execution time Memory
33338 2017-10-24T06:49:34 Z ngkan146 Soccer (JOI17_soccer) C++
0 / 100
 3000 ms 22856 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,int> ii;
#define fi first
#define se second
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
ll A,B,C;
int n,h,w;
ll dp0[505][505], dp1[505][505][4];
bool player[505][505];
int min_distance[505][505];
void prep(){
	queue <int> q;
	for(int i=0;i<=h;i++)
		for(int j=0;j<=w;j++){
			if (player[i][j]) min_distance[i][j] = 0, q.push(i * 501 + j);
			else min_distance[i][j] = 100000;
		}
	while(q.size()){
		int x = q.front() / 501;
		int y = q.front() % 501;
		q.pop();
		for(int k=0;k<4;k++){
			int X = x + dx[k];
			int Y = y + dy[k];
			if (0 > X || X > h || 0 > Y || Y > w) continue;
			if (min_distance[X][Y] > min_distance[x][y] + 1)
				min_distance[X][Y] = min_distance[x][y] + 1,
				q.push(X * 501 + Y);
		}
	}
}
#define x1 asd
#define y1 jnda
#define xn addaf
#define yn nln
int x1,y1,xn,yn;
void prep_dp(){
	for(int i=0;i<=h;i++)
		for(int j=0;j<=w;j++)
			dp0[i][j] = dp1[i][j][0] = dp1[i][j][1] = dp1[i][j][2] = dp1[i][j][3] = (ll) 1e18;
	dp0[x1][y1] = 0;
}
bool visited[5][505][505];
void cal_dp(){
	for(int _time=0;_time<=h+w;_time++){
		priority_queue <ii,vector<ii>,greater<ii> > pq;
		for(int i=0;i<=h;i++)
			for(int j=0;j<=w;j++)
				pq.push(ii(dp0[i][j], i*3500 + j * 5 + 0));
		
		while(pq.size()){
			int x = pq.top().se / 3500;
			int y = (pq.top().se % 3500) / 5;
			int type = pq.top().se % 5;
			
			pq.pop();
			if (visited[type][x][y]) continue;
			visited[type][x][y] = 1;
			
			if (type == 0){
				for(int k=0;k<4;k++){
					int X = x + dx[k];
					int Y = y + dy[k];
					if (0 > X || X > h || 0 > Y || Y > w) continue;
					if (dp1[X][Y][k] > dp0[x][y] + A + B)
						dp1[X][Y][k] = dp0[x][y] + A + B,
						pq.push(ii(dp1[X][Y][k], X * 3500 + Y * 5 + k+1));
					if (dp0[X][Y] > dp0[x][y] + C)
						dp0[X][Y] = dp0[x][y] + C,
						pq.push(ii(dp0[X][Y], X * 3500 + Y * 5 + k+1));
				}
			}
			else{
				int X = x + dx[type-1];
				int Y = y + dy[type-1];
				if (0 > X || X > h || 0 > Y || Y > w) continue;
				if (dp1[X][Y][type-1] > dp1[x][y][type-1] + A)
					dp1[X][Y][type-1] = dp1[x][y][type-1] + A,
					pq.push(ii(dp1[X][Y][type-1], X * 3500 + Y * 5 + type));
			}
		}
		
		
		for(int i=0;i<=h;i++)
			for(int j=0;j<=w;j++)
				for(int t=0;t<4;t++)
					dp0[i][j] = min(dp0[i][j], dp1[i][j][t] + min_distance[i][j] * C),
					dp1[i][j][t] = (ll) 1e18;
					
		memset(visited,0,sizeof(visited));
		//for(int i=0;i<=h;i++){
		//	for(int j=0;j<=w;j++){
		//		if (dp0[i][j] != (ll) 1e18) cout << dp0[i][j] << ' ';
		//		else cout << -1;
		//	}
		//	cout << endl;
		//}
		//cout << endl;
	}
}
int main(){
	iostream::sync_with_stdio(0);
	cin >> h >> w;
	cin >> A >> B >> C;
	cin >> n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin >> x >> y; 
		if (i == 1) x1 = x, y1 = y;
		if (i == n) xn = x, yn = y;
		player[x][y] = 1;
	}
	prep();
	prep_dp();
	cal_dp();
	cout << dp0[xn][yn];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 16712 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 22856 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 16712 KB Execution timed out
2 Halted 0 ms 0 KB -