oj.uz

Submission #33343

# Submission time Handle Problem Language Result Execution time Memory
33343 2017-10-24T07:56:51 Z ngkan146 Soccer (JOI17_soccer) C++
100 / 100
 559 ms 19572 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  markh[505], markw[505];

void cal_dp(){
	priority_queue <ii,vector<ii>,greater<ii> > pq;
	
	pq.push(ii(0, x1 * 3500 + y1 * 5));
		
	while(pq.size()){
		int x = pq.top().se / 3500;
		int y = (pq.top().se % 3500) / 5;
		int type = pq.top().se % 5;
		ll dis = pq.top().fi;
		pq.pop();
		
		if (type == 0 && dp0[x][y] != dis) continue;
		if (type && dp1[x][y][type-1] != dis) continue;
		
		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 + 0));
			}
		}
		else{
			int X = x + dx[type-1];
			int Y = y + dy[type-1];
			if (dp1[x][y][type-1] + min_distance[x][y] * C < dp0[x][y])
				dp0[x][y] = dp1[x][y][type-1] + min_distance[x][y] * C,
				pq.push(ii(dp0[x][y], x*3500 + y*5));
			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));
			
		}
	}
}
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];
}
/*
500 500 
1 3 6
3
1 1
0 4
6 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14964 KB Output is correct
2 Correct 0 ms 13388 KB Output is correct
3 Correct 329 ms 19572 KB Output is correct
4 Correct 359 ms 19572 KB Output is correct
5 Correct 83 ms 13548 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 19572 KB Output is correct
2 Correct 366 ms 19572 KB Output is correct
3 Correct 279 ms 19572 KB Output is correct
4 Correct 276 ms 19572 KB Output is correct
5 Correct 296 ms 19572 KB Output is correct
6 Correct 359 ms 19572 KB Output is correct
7 Correct 386 ms 19572 KB Output is correct
8 Correct 346 ms 19572 KB Output is correct
9 Correct 379 ms 19572 KB Output is correct
10 Correct 53 ms 14964 KB Output is correct
11 Correct 386 ms 19572 KB Output is correct
12 Correct 336 ms 19572 KB Output is correct
13 Correct 219 ms 19572 KB Output is correct
14 Correct 329 ms 19572 KB Output is correct
15 Correct 283 ms 19572 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14964 KB Output is correct
2 Correct 0 ms 13388 KB Output is correct
3 Correct 329 ms 19572 KB Output is correct
4 Correct 359 ms 19572 KB Output is correct
5 Correct 83 ms 13548 KB Output is correct
6 Correct 419 ms 19572 KB Output is correct
7 Correct 366 ms 19572 KB Output is correct
8 Correct 279 ms 19572 KB Output is correct
9 Correct 276 ms 19572 KB Output is correct
10 Correct 296 ms 19572 KB Output is correct
11 Correct 359 ms 19572 KB Output is correct
12 Correct 386 ms 19572 KB Output is correct
13 Correct 346 ms 19572 KB Output is correct
14 Correct 379 ms 19572 KB Output is correct
15 Correct 53 ms 14964 KB Output is correct
16 Correct 386 ms 19572 KB Output is correct
17 Correct 336 ms 19572 KB Output is correct
18 Correct 219 ms 19572 KB Output is correct
19 Correct 329 ms 19572 KB Output is correct
20 Correct 283 ms 19572 KB Output is correct
21 Correct 89 ms 14196 KB Output is correct
22 Correct 446 ms 19572 KB Output is correct
23 Correct 459 ms 16500 KB Output is correct
24 Correct 533 ms 16500 KB Output is correct
25 Correct 416 ms 19572 KB Output is correct
26 Correct 499 ms 19572 KB Output is correct
27 Correct 233 ms 13932 KB Output is correct
28 Correct 303 ms 13920 KB Output is correct
29 Correct 449 ms 16500 KB Output is correct
30 Correct 266 ms 13656 KB Output is correct
31 Correct 476 ms 19572 KB Output is correct
32 Correct 553 ms 19572 KB Output is correct
33 Correct 363 ms 19572 KB Output is correct
34 Correct 559 ms 19572 KB Output is correct
35 Correct 246 ms 13552 KB Output is correct