oj.uz

Submission #248928

# Submission time Handle Problem Language Result Execution time Memory
248928 2020-07-13T18:22:15 Z pit4h Soccer (JOI17_soccer) C++14
35 / 100
 2438 ms 262148 KB 
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>

using ll = long long;
using namespace std;

const int H=502, N=1e5+2;
const ll INF = 1e12+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)) continue;
				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 318 ms 7408 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2327 ms 12560 KB Output is correct
4 Correct 2279 ms 16816 KB Output is correct
5 Correct 515 ms 8176 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2230 ms 12776 KB Output is correct
2 Correct 2395 ms 12776 KB Output is correct
3 Correct 1723 ms 11372 KB Output is correct
4 Correct 2147 ms 12776 KB Output is correct
5 Correct 1744 ms 12776 KB Output is correct
6 Correct 2438 ms 12776 KB Output is correct
7 Correct 2232 ms 13036 KB Output is correct
8 Correct 2153 ms 12912 KB Output is correct
9 Correct 2263 ms 12908 KB Output is correct
10 Correct 284 ms 9844 KB Output is correct
11 Correct 2285 ms 12908 KB Output is correct
12 Correct 2182 ms 12908 KB Output is correct
13 Correct 1650 ms 11240 KB Output is correct
14 Correct 2272 ms 13020 KB Output is correct
15 Correct 1762 ms 13036 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 7408 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2327 ms 12560 KB Output is correct
4 Correct 2279 ms 16816 KB Output is correct
5 Correct 515 ms 8176 KB Output is correct
6 Correct 2230 ms 12776 KB Output is correct
7 Correct 2395 ms 12776 KB Output is correct
8 Correct 1723 ms 11372 KB Output is correct
9 Correct 2147 ms 12776 KB Output is correct
10 Correct 1744 ms 12776 KB Output is correct
11 Correct 2438 ms 12776 KB Output is correct
12 Correct 2232 ms 13036 KB Output is correct
13 Correct 2153 ms 12912 KB Output is correct
14 Correct 2263 ms 12908 KB Output is correct
15 Correct 284 ms 9844 KB Output is correct
16 Correct 2285 ms 12908 KB Output is correct
17 Correct 2182 ms 12908 KB Output is correct
18 Correct 1650 ms 11240 KB Output is correct
19 Correct 2272 ms 13020 KB Output is correct
20 Correct 1762 ms 13036 KB Output is correct
21 Runtime error 648 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -