oj.uz

Submission #248963

# Submission time Handle Problem Language Result Execution time Memory
248963 2020-07-13T19:02:41 Z pit4h Soccer (JOI17_soccer) C++14
100 / 100
 1567 ms 10504 KB 
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>

using ll = long long;
using namespace std;

const int H=503, N=1e5+2;
const ll INF = 5e12+1;
int h, w, n, s[N], t[N];
ll a, b, c;
bool player[H][H];

ll closest[H][H];
ll minX[H][H], maxX[H][H];

bool vis[H][H];
ll dist[H][H];
ll minimal[H];

struct Obj {
	ll d;
	int x, y;
	
	bool operator<(Obj o) const{
		return d > o.d;	
	}
};

Obj Find_best() {
	ll mini = INF;
	int cord=-1;
	for(int i=1; i<=h; ++i) {
		if(mini > minimal[i]) {
			mini = minimal[i];
			cord = i;
		}
	}
	Obj res;
	res.d = mini;
	res.x = cord;
	res.y = -1;
	if(mini == INF) return res;
	for(int i=1; i<=w; ++i) {
		if(!vis[cord][i] && dist[cord][i] == minimal[cord]) {
			res.y=i;
			break;
		}
	}
	vis[res.x][res.y] = 1;
	minimal[cord] = INF;
	for(int i=1; i<=w; ++i) {
		if(!vis[cord][i]) {
			minimal[cord] = min(minimal[cord], dist[cord][i]);
		}
	}
	return res;
}

vector<int> moveX = {0, 0, 1, -1}, moveY = {1, -1, 0, 0};

bool inside(int x, int y) {
	if(x>=1 && x<=h && y>=1 && y<=w) return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>h>>w;
	cin>>a>>b>>c;
	cin>>n;
	h++;
	w++;

	for(int i=0; i<n; ++i) { 
		cin>>s[i]>>t[i];	
		s[i]++;
		t[i]++;
		player[s[i]][t[i]] = 1;
	}

	for(int i=1; i<=w; ++i) {
		maxX[0][i] = -INF;
	}
	for(int x=1; x<=h; ++x) {
		for(int y=1; y<=w; ++y) {
			if(player[x][y]) maxX[x][y] = x;
			else maxX[x][y] = maxX[x-1][y];
		}
	}

	for(int i=1; i<=w; ++i) {	
		minX[h+1][i] = INF;
	}
	for(int x=h; x>=1; --x) {
		for(int y=1; y<=w; ++y) {
			if(player[x][y]) minX[x][y] = x;
			else minX[x][y] = minX[x+1][y];
		}
	}

	for(int x=1; x<=h; ++x) {
		for(int y=1; y<=w; ++y) {
			closest[x][y] = INF;
			for(int i=1; i<=w; ++i) {
				closest[x][y] = min(closest[x][y], abs(y-i) + min( x - maxX[x][i], minX[x][i] - x));
			}
		}
	}

	for(int i=1; i<=h; ++i) {
		for(int j=1; j<=w; ++j) {
			dist[i][j] = INF;
		}
	}
	
	dist[s[0]][t[0]] = 0;

	for(int i=1; i<=h; ++i) {
		minimal[i] = INF;
	}
	minimal[s[0]] = 0;
	while(true) {
		auto cur = Find_best();
		ll d = cur.d;
		if(d==INF) break;
		int x = cur.x;
		int y = cur.y;
		// C
		for(int i=0; i<4; ++i) {
			int nx = x+moveX[i], ny = y+moveY[i];
			if(inside(nx, ny) && d + c < dist[nx][ny]) {
				dist[nx][ny] = d + c;
				minimal[nx] = min(minimal[nx], dist[nx][ny]);
			}
		}

		//Ax + B
		for(int i=0; i<4; ++i) {
			for(int p=1; p<=max(h, w); ++p) {
				int nx = x+p*moveX[i], ny = y+p*moveY[i];
				if(!inside(nx, ny)) break;
				ll nd = d + a*p + b + c * closest[nx][ny];
				if(nd < dist[nx][ny]) {
					dist[nx][ny] = nd;
					minimal[nx] = min(minimal[nx], dist[nx][ny]);
				}
			}
		}
			
	}
	
	cout<<dist[s[n-1]][t[n-1]];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 5240 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1395 ms 8668 KB Output is correct
4 Correct 1430 ms 8568 KB Output is correct
5 Correct 314 ms 6136 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 8824 KB Output is correct
2 Correct 1400 ms 8676 KB Output is correct
3 Correct 1031 ms 7160 KB Output is correct
4 Correct 1333 ms 8696 KB Output is correct
5 Correct 1018 ms 8824 KB Output is correct
6 Correct 1443 ms 8892 KB Output is correct
7 Correct 1476 ms 8824 KB Output is correct
8 Correct 1387 ms 8824 KB Output is correct
9 Correct 1454 ms 8824 KB Output is correct
10 Correct 110 ms 8704 KB Output is correct
11 Correct 1450 ms 8824 KB Output is correct
12 Correct 1394 ms 8824 KB Output is correct
13 Correct 1047 ms 7168 KB Output is correct
14 Correct 1465 ms 8828 KB Output is correct
15 Correct 1010 ms 8824 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 5240 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1395 ms 8668 KB Output is correct
4 Correct 1430 ms 8568 KB Output is correct
5 Correct 314 ms 6136 KB Output is correct
6 Correct 1437 ms 8824 KB Output is correct
7 Correct 1400 ms 8676 KB Output is correct
8 Correct 1031 ms 7160 KB Output is correct
9 Correct 1333 ms 8696 KB Output is correct
10 Correct 1018 ms 8824 KB Output is correct
11 Correct 1443 ms 8892 KB Output is correct
12 Correct 1476 ms 8824 KB Output is correct
13 Correct 1387 ms 8824 KB Output is correct
14 Correct 1454 ms 8824 KB Output is correct
15 Correct 110 ms 8704 KB Output is correct
16 Correct 1450 ms 8824 KB Output is correct
17 Correct 1394 ms 8824 KB Output is correct
18 Correct 1047 ms 7168 KB Output is correct
19 Correct 1465 ms 8828 KB Output is correct
20 Correct 1010 ms 8824 KB Output is correct
21 Correct 325 ms 5320 KB Output is correct
22 Correct 1426 ms 8872 KB Output is correct
23 Correct 1250 ms 8080 KB Output is correct
24 Correct 1567 ms 8952 KB Output is correct
25 Correct 1481 ms 8964 KB Output is correct
26 Correct 1484 ms 8952 KB Output is correct
27 Correct 1487 ms 9968 KB Output is correct
28 Correct 1456 ms 10360 KB Output is correct
29 Correct 1418 ms 10476 KB Output is correct
30 Correct 1396 ms 10352 KB Output is correct
31 Correct 1512 ms 8952 KB Output is correct
32 Correct 1539 ms 10360 KB Output is correct
33 Correct 1372 ms 8900 KB Output is correct
34 Correct 1469 ms 8864 KB Output is correct
35 Correct 1364 ms 10504 KB Output is correct