oj.uz

Submission #248940

# Submission time Handle Problem Language Result Execution time Memory
248940 2020-07-13T18:27:50 Z pit4h Soccer (JOI17_soccer) C++14
35 / 100
 1628 ms 262144 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];
struct Obj {
	ll d;
	int x, y;
	
	bool operator<(Obj o) const{
		return d > o.d;	
	}
};

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;
		}
	}
	
	priority_queue< Obj > Q;
	Q.push({0, s[0], t[0]});
	dist[s[0]][t[0]] = 0;

	while(Q.size()) {
		auto cur = Q.top();
		Q.pop();
		ll d = cur.d;
		int x = cur.x;
		int y = cur.y;
		if(vis[x][y]) continue;
		vis[x][y] = 1;
		
		// 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;
				Q.push({d+c, 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;
					Q.push({nd, nx, ny});
				}
			}
		}
			
	}
	
	cout<<dist[s[n-1]][t[n-1]];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 7660 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1546 ms 12644 KB Output is correct
4 Correct 1586 ms 16864 KB Output is correct
5 Correct 339 ms 8176 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1541 ms 12776 KB Output is correct
2 Correct 1615 ms 12928 KB Output is correct
3 Correct 1079 ms 11236 KB Output is correct
4 Correct 1428 ms 12936 KB Output is correct
5 Correct 1057 ms 12908 KB Output is correct
6 Correct 1497 ms 12904 KB Output is correct
7 Correct 1548 ms 13036 KB Output is correct
8 Correct 1528 ms 12996 KB Output is correct
9 Correct 1527 ms 12908 KB Output is correct
10 Correct 125 ms 9852 KB Output is correct
11 Correct 1496 ms 13036 KB Output is correct
12 Correct 1498 ms 12908 KB Output is correct
13 Correct 1052 ms 11368 KB Output is correct
14 Correct 1628 ms 13060 KB Output is correct
15 Correct 1056 ms 13036 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 7660 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1546 ms 12644 KB Output is correct
4 Correct 1586 ms 16864 KB Output is correct
5 Correct 339 ms 8176 KB Output is correct
6 Correct 1541 ms 12776 KB Output is correct
7 Correct 1615 ms 12928 KB Output is correct
8 Correct 1079 ms 11236 KB Output is correct
9 Correct 1428 ms 12936 KB Output is correct
10 Correct 1057 ms 12908 KB Output is correct
11 Correct 1497 ms 12904 KB Output is correct
12 Correct 1548 ms 13036 KB Output is correct
13 Correct 1528 ms 12996 KB Output is correct
14 Correct 1527 ms 12908 KB Output is correct
15 Correct 125 ms 9852 KB Output is correct
16 Correct 1496 ms 13036 KB Output is correct
17 Correct 1498 ms 12908 KB Output is correct
18 Correct 1052 ms 11368 KB Output is correct
19 Correct 1628 ms 13060 KB Output is correct
20 Correct 1056 ms 13036 KB Output is correct
21 Runtime error 547 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -