답안 #1087844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087844	2024-09-13T10:08:14 Z	mychecksedad	Toy (CEOI24_toy)	C++17	0 / 100	18 ms	12796 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define en cout << '\n'
#define vi vector<int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 1500+100;


int n, m, k, l, xh, yh, xv, yv, pref[N][N], H[N][N], V[N][N], vis[N][N], L[N][N], R[N][N], U[N][N], D[N][N];
string s[N];
int arr[4][2]={
	{0, 1},
	{1, 0},
	{-1, 0},
	{0, -1}
};
int get(int r1, int r2, int c1, int c2){
	return pref[r2][c2] - pref[r1 - 1][c2] - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1];
}
void solve(){
	cin >> m >> n >> k >> l;	
	cin >> yh >> xh >> yv >> xv;
	++xh, ++yh, ++xv, ++yv;
	for(int i = 1; i <= n; ++i){
		cin >> s[i];
		s[i] = " " + s[i];
	}
	for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) pref[i][j] = 0;
	for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) H[i][j] = V[i][j] = vis[i][j] = L[i][j] = R[i][j] = D[i][j] = U[i][j] = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
			if(s[i][j] == 'X') ++pref[i][j];
		}
	}
	H[xh][yh] = 1;
	queue<pii> q;
	q.push({xh, yh});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx <= n && ny + k - 1 <= m && H[nx][ny] == 0){
				if(get(nx, nx, ny, ny + k - 1) == 0){
					H[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}
	V[xv][yv] = 1;
	q.push({xv, yv});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx + l - 1 <= n && ny <= m && V[nx][ny] == 0){
				if(get(nx, nx+l-1, ny, ny) == 0){
					V[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}

	for(int i = n; i >= 1; --i){
		for(int j = m; j >= 1; --j){
			for(int i1 = i; i1 >= max(1, i - l + 1); --i1)
					if(get(i1, i, j, j) == 0 && V[i1][j]){
						if(V[i1][j + 1]) R[i][j] = 1;
						if(V[i1][j - 1]) L[i][j] = 1;
					}
			for(int i1 = j; i1 >= max(1, j - k + 1); --i1)
					if(get(i, i, i1, j) == 0 && H[i][i1]){
						if(H[i - 1][i1]) U[i][j] = 1;
						if(H[i + 1][i1]) D[i][j] = 1;
					}
		}
	}
	// for(int i = 1; i <= n; ++i){
	// 	for(int j = 1; j <= m; ++j){
	// 		cout << L[i][j];
	// 	}
	// 	en;
	// }
	// assert(H[xh][yv] && V[xh][yv]);
	vis[xh][yv] = 1;
	q.push({xh, yv});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx <= n && ny <= m && !vis[nx][ny]){
				if((nx == x - 1 && L[x][y]) || (nx == x + 1 && R[x][y]) || (ny == y + 1 && D[x][y]) || (ny == y - 1 && U[x][y])){
					vis[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(s[i][j] == '*' && vis[i][j]){
				cout << "YES";
				return;
			}
		}
	}
	cout << "NO";
}

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct

Subtask #1
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	1 ms	2140 KB	Output is correct
5	Correct	1 ms	2140 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	2140 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1624 KB	Output is correct
10	Correct	1 ms	2140 KB	Output is correct
11	Correct	1 ms	2140 KB	Output is correct
12	Correct	0 ms	772 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2140 KB	Output is correct
15	Correct	1 ms	2140 KB	Output is correct
16	Correct	1 ms	1884 KB	Output is correct
17	Correct	1 ms	1884 KB	Output is correct
18	Correct	1 ms	2136 KB	Output is correct
19	Correct	1 ms	2140 KB	Output is correct
20	Correct	1 ms	2140 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	1 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	1 ms	1964 KB	Output is correct
26	Correct	1 ms	2136 KB	Output is correct
27	Correct	1 ms	2136 KB	Output is correct
28	Correct	1 ms	2392 KB	Output is correct
29	Correct	1 ms	2140 KB	Output is correct
30	Correct	1 ms	1884 KB	Output is correct
31	Incorrect	1 ms	1884 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	1 ms	2140 KB	Output is correct
5	Correct	1 ms	2140 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	2140 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1624 KB	Output is correct
10	Correct	1 ms	2140 KB	Output is correct
11	Correct	1 ms	2140 KB	Output is correct
12	Correct	0 ms	772 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2140 KB	Output is correct
15	Correct	1 ms	2140 KB	Output is correct
16	Correct	1 ms	1884 KB	Output is correct
17	Correct	1 ms	1884 KB	Output is correct
18	Correct	1 ms	2136 KB	Output is correct
19	Correct	1 ms	2140 KB	Output is correct
20	Correct	1 ms	2140 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	1 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	1 ms	1964 KB	Output is correct
26	Correct	1 ms	2136 KB	Output is correct
27	Correct	1 ms	2136 KB	Output is correct
28	Correct	1 ms	2392 KB	Output is correct
29	Correct	1 ms	2140 KB	Output is correct
30	Correct	1 ms	1884 KB	Output is correct
31	Incorrect	1 ms	1884 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #3
0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	1 ms	1628 KB	Output is correct
4	Correct	10 ms	12796 KB	Output is correct
5	Correct	12 ms	12632 KB	Output is correct
6	Correct	2 ms	2908 KB	Output is correct
7	Correct	13 ms	12632 KB	Output is correct
8	Correct	13 ms	12636 KB	Output is correct
9	Correct	3 ms	5056 KB	Output is correct
10	Correct	9 ms	12636 KB	Output is correct
11	Correct	7 ms	12636 KB	Output is correct
12	Correct	4 ms	8968 KB	Output is correct
13	Correct	7 ms	12656 KB	Output is correct
14	Correct	8 ms	12636 KB	Output is correct
15	Correct	18 ms	12380 KB	Output is correct
16	Correct	11 ms	12128 KB	Output is correct
17	Correct	11 ms	12636 KB	Output is correct
18	Correct	11 ms	12772 KB	Output is correct
19	Correct	11 ms	12788 KB	Output is correct
20	Correct	11 ms	12636 KB	Output is correct
21	Correct	14 ms	12560 KB	Output is correct
22	Correct	12 ms	12632 KB	Output is correct
23	Correct	11 ms	12796 KB	Output is correct
24	Correct	11 ms	12636 KB	Output is correct
25	Correct	11 ms	12556 KB	Output is correct
26	Correct	11 ms	12792 KB	Output is correct
27	Correct	12 ms	12636 KB	Output is correct
28	Correct	11 ms	12796 KB	Output is correct
29	Correct	11 ms	12796 KB	Output is correct
30	Correct	10 ms	12376 KB	Output is correct
31	Incorrect	9 ms	12376 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	1 ms	2140 KB	Output is correct
5	Correct	1 ms	2140 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	2140 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1624 KB	Output is correct
10	Correct	1 ms	2140 KB	Output is correct
11	Correct	1 ms	2140 KB	Output is correct
12	Correct	0 ms	772 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2140 KB	Output is correct
15	Correct	1 ms	2140 KB	Output is correct
16	Correct	1 ms	1884 KB	Output is correct
17	Correct	1 ms	1884 KB	Output is correct
18	Correct	1 ms	2136 KB	Output is correct
19	Correct	1 ms	2140 KB	Output is correct
20	Correct	1 ms	2140 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	1 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	1 ms	1964 KB	Output is correct
26	Correct	1 ms	2136 KB	Output is correct
27	Correct	1 ms	2136 KB	Output is correct
28	Correct	1 ms	2392 KB	Output is correct
29	Correct	1 ms	2140 KB	Output is correct
30	Correct	1 ms	1884 KB	Output is correct
31	Incorrect	1 ms	1884 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	1 ms	2140 KB	Output is correct
5	Correct	1 ms	2140 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	2140 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1624 KB	Output is correct
10	Correct	1 ms	2140 KB	Output is correct
11	Correct	1 ms	2140 KB	Output is correct
12	Correct	0 ms	772 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2140 KB	Output is correct
15	Correct	1 ms	2140 KB	Output is correct
16	Correct	1 ms	1884 KB	Output is correct
17	Correct	1 ms	1884 KB	Output is correct
18	Correct	1 ms	2136 KB	Output is correct
19	Correct	1 ms	2140 KB	Output is correct
20	Correct	1 ms	2140 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	1 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	1 ms	1964 KB	Output is correct
26	Correct	1 ms	2136 KB	Output is correct
27	Correct	1 ms	2136 KB	Output is correct
28	Correct	1 ms	2392 KB	Output is correct
29	Correct	1 ms	2140 KB	Output is correct
30	Correct	1 ms	1884 KB	Output is correct
31	Incorrect	1 ms	1884 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #1087844

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 0.0 / 14.0

Subtask #2 0.0 / 21.0

Subtask #3 0.0 / 9.0

Subtask #4 0.0 / 29.0

Subtask #5 0.0 / 27.0

Subtask #0
0.0 / 0.0

Subtask #1
0.0 / 14.0

Subtask #2
0.0 / 21.0

Subtask #3
0.0 / 9.0

Subtask #4
0.0 / 29.0

Subtask #5
0.0 / 27.0