답안 #1087846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087846	2024-09-13T10:09:49 Z	mychecksedad	Toy (CEOI24_toy)	C++17	0 / 100	14 ms	12800 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 && R[x][y]) || (nx == x + 1 && L[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	1 ms	856 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	1628 KB	Output is correct
10	Correct	2 ms	1984 KB	Output is correct
11	Correct	1 ms	2136 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	1 ms	2140 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	2176 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	2140 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	1 ms	2140 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	1 ms	856 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	1628 KB	Output is correct
10	Correct	2 ms	1984 KB	Output is correct
11	Correct	1 ms	2136 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	1 ms	2140 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	2176 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	2140 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	1 ms	2140 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	12800 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	12 ms	12792 KB	Output is correct
9	Correct	3 ms	4952 KB	Output is correct
10	Correct	9 ms	12636 KB	Output is correct
11	Correct	10 ms	12636 KB	Output is correct
12	Correct	4 ms	9080 KB	Output is correct
13	Correct	7 ms	12636 KB	Output is correct
14	Correct	8 ms	12636 KB	Output is correct
15	Correct	12 ms	12628 KB	Output is correct
16	Correct	11 ms	12120 KB	Output is correct
17	Correct	11 ms	12636 KB	Output is correct
18	Correct	11 ms	12792 KB	Output is correct
19	Correct	11 ms	12736 KB	Output is correct
20	Correct	11 ms	12632 KB	Output is correct
21	Correct	12 ms	12656 KB	Output is correct
22	Correct	11 ms	12796 KB	Output is correct
23	Correct	11 ms	12796 KB	Output is correct
24	Correct	12 ms	12560 KB	Output is correct
25	Correct	14 ms	12636 KB	Output is correct
26	Correct	11 ms	12636 KB	Output is correct
27	Correct	11 ms	12796 KB	Output is correct
28	Correct	11 ms	12636 KB	Output is correct
29	Correct	10 ms	12636 KB	Output is correct
30	Correct	11 ms	12364 KB	Output is correct
31	Incorrect	11 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	1 ms	856 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	1628 KB	Output is correct
10	Correct	2 ms	1984 KB	Output is correct
11	Correct	1 ms	2136 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	1 ms	2140 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	2176 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	2140 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	1 ms	2140 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	1 ms	856 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	1628 KB	Output is correct
10	Correct	2 ms	1984 KB	Output is correct
11	Correct	1 ms	2136 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	1 ms	2140 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	2176 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	2140 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	1 ms	2140 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	-

답안 #1087846

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