Submission #1045728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045728		alex_2008	Toy (CEOI24_toy)	C++14	100 / 100	147 ms	40532 KiB

Main

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
typedef long long ll;
using namespace std;
const int N = 1510;
char a[N][N];
bool used[N][N];
int tp[N][N];
int dwn[N][N];
int lft[N][N];
int rght[N][N];
int w, h, k, l;
int cnt(int x1, int y1, int x2, int y2) {
	return a[x2][y2] - a[x1][y2] - a[x2][y1] + a[x1][y1];
}
pair<int, int> vertical_range(int x, int y) {
	if (tp[x][y] + dwn[x][y] <= l) return { 1, 0 };
	int r_min = x - tp[x][y] + 1;
	int r_mx = x + dwn[x][y] - l;
	return make_pair(r_min, r_mx);
}
pair<int, int> horizontal_range(int x, int y) {
	if (lft[x][y] + rght[x][y] <= k) return { 1, 0 };
	int c_min = y - lft[x][y] + 1;
	int c_mx = y + rght[x][y] - k;
	return make_pair(c_min, c_mx);
}
bool intersect(pair<int, int> x, pair<int, int> y) {
	pair<int, int> c = make_pair(max(x.first, y.first), min(x.second, y.second));
	if (c.first > c.second) return false;
	return true;
}
bool ch(int x, int y) {
	if ((tp[x][y] + dwn[x][y]) > l && (lft[x][y] + rght[x][y]) > k) return true;
	return false;
}
int main() {
	cin >> w >> h >> k >> l;
	int xh, yh, xv, yv;
	cin >> xh >> yh >> xv >> yv;
	xh++; xv++; yh++; yv++;
	swap(xh, yh); swap(xv, yv);
	//cout << xh << " " << yh << " " << xv << " " << yv << "\n";
	int fx = -1, fy = -1;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> a[i][j];
			if (a[i][j] == '*') {
				fx = i;
				fy = j;
			}
		}
	}

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (a[i][j] == 'X') {
				lft[i][j] = 0;
				tp[i][j] = 0;
			}
			else {
				lft[i][j] = lft[i][j - 1] + 1;
				tp[i][j] = tp[i - 1][j] + 1;
			}
			lft[i][j] = min(lft[i][j], k);
			tp[i][j] = min(tp[i][j], l);

		}
	}
	for (int i = h; i >= 1; i--) {
		for (int j = w; j >= 1; j--) {
			if (a[i][j] == 'X') {
				rght[i][j] = 0;
				dwn[i][j] = 0;
			}
			else {
				rght[i][j] = rght[i][j + 1] + 1;
				dwn[i][j] = dwn[i + 1][j] + 1;
			}
			rght[i][j] = min(rght[i][j], k);
			dwn[i][j] = min(dwn[i][j], l);
		}
	}
	used[xh][yv] = true;
	queue <pair<int, int>> Q;
	Q.push({ xh, yv });
	while (!Q.empty()) {
		int x = Q.front().first, y = Q.front().second; Q.pop();
		if (x > 1) {
			if (intersect(horizontal_range(x, y), horizontal_range(x - 1, y)) && ch(x - 1, y)) {
				if (!used[x - 1][y]) {
					used[x - 1][y] = true;
					Q.push({ x - 1, y });
				}
			}
		}
		if (x < h) {
			if (intersect(horizontal_range(x, y), horizontal_range(x + 1, y)) && ch(x + 1, y)) {
				if (!used[x + 1][y]) {
					used[x + 1][y] = true;
					Q.push({ x + 1, y });
				}
			}
		}
		if (y > 1) {
			if (intersect(vertical_range(x, y), vertical_range(x, y - 1)) && ch(x, y - 1)) {
				if (!used[x][y - 1]) {
					used[x][y - 1] = true;
					Q.push({ x, y - 1 });
				}
			}
		}
		if (y < w) {
			if (intersect(vertical_range(x, y), vertical_range(x, y + 1)) && ch(x, y + 1)) {
				if (!used[x][y + 1]) {
					used[x][y + 1] = true;
					Q.push({ x, y + 1 });
				}
			}
		}
	}
	if (used[fx][fy]) cout << "YES\n";
	else cout << "NO\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27