oj.uz

Submission #248933

# Submission time Handle Problem Language Result Execution time Memory
248933 2020-07-13T18:24:42 Z pit4h Soccer (JOI17_soccer) C++14
35 / 100
 1892 ms 262148 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;
	
	friend bool operator<(const Obj& o1, const Obj& o2) {
		return o1.d > o2.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 196 ms 7380 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1892 ms 12588 KB Output is correct
4 Correct 1598 ms 16736 KB Output is correct
5 Correct 351 ms 8172 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1544 ms 12772 KB Output is correct
2 Correct 1786 ms 12780 KB Output is correct
3 Correct 1089 ms 11240 KB Output is correct
4 Correct 1436 ms 12776 KB Output is correct
5 Correct 1051 ms 12904 KB Output is correct
6 Correct 1513 ms 12908 KB Output is correct
7 Correct 1621 ms 13292 KB Output is correct
8 Correct 1525 ms 12908 KB Output is correct
9 Correct 1574 ms 12908 KB Output is correct
10 Correct 139 ms 9852 KB Output is correct
11 Correct 1551 ms 12908 KB Output is correct
12 Correct 1539 ms 12908 KB Output is correct
13 Correct 1037 ms 11244 KB Output is correct
14 Correct 1554 ms 13164 KB Output is correct
15 Correct 1084 ms 13036 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 7380 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1892 ms 12588 KB Output is correct
4 Correct 1598 ms 16736 KB Output is correct
5 Correct 351 ms 8172 KB Output is correct
6 Correct 1544 ms 12772 KB Output is correct
7 Correct 1786 ms 12780 KB Output is correct
8 Correct 1089 ms 11240 KB Output is correct
9 Correct 1436 ms 12776 KB Output is correct
10 Correct 1051 ms 12904 KB Output is correct
11 Correct 1513 ms 12908 KB Output is correct
12 Correct 1621 ms 13292 KB Output is correct
13 Correct 1525 ms 12908 KB Output is correct
14 Correct 1574 ms 12908 KB Output is correct
15 Correct 139 ms 9852 KB Output is correct
16 Correct 1551 ms 12908 KB Output is correct
17 Correct 1539 ms 12908 KB Output is correct
18 Correct 1037 ms 11244 KB Output is correct
19 Correct 1554 ms 13164 KB Output is correct
20 Correct 1084 ms 13036 KB Output is correct
21 Runtime error 530 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -