Submission #248963

#	Time	Username	Problem	Language	Result	Execution time	Memory
248963		pit4h	Soccer (JOI17_soccer)	C++14	100 / 100	1567 ms	10504 KiB

soccer

#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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65