답안 #1087845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087845	2024-09-13T10:08:39 Z	mychecksedad	Toy (CEOI24_toy)	C++17	0 / 100	12 ms	12712 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 && U[x][y]) || (ny == y - 1 && D[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	1 ms	604 KB	Output is correct
2	Correct	0 ms	616 KB	Output is correct

Subtask #1
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	616 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	2 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	2 ms	2392 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1628 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	604 KB	Output is correct
13	Correct	2 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	1992 KB	Output is correct
18	Correct	1 ms	2140 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	2136 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	2 ms	2136 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	1880 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	616 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	2 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	2 ms	2392 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1628 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	604 KB	Output is correct
13	Correct	2 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	1992 KB	Output is correct
18	Correct	1 ms	2140 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	2136 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	2 ms	2136 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	1880 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #3
0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	616 KB	Output is correct
3	Correct	1 ms	1628 KB	Output is correct
4	Correct	11 ms	12704 KB	Output is correct
5	Correct	11 ms	12636 KB	Output is correct
6	Correct	2 ms	2908 KB	Output is correct
7	Correct	12 ms	12636 KB	Output is correct
8	Correct	12 ms	12700 KB	Output is correct
9	Correct	2 ms	4956 KB	Output is correct
10	Correct	8 ms	12636 KB	Output is correct
11	Correct	7 ms	12636 KB	Output is correct
12	Correct	3 ms	9052 KB	Output is correct
13	Correct	7 ms	12632 KB	Output is correct
14	Correct	7 ms	12636 KB	Output is correct
15	Correct	10 ms	12540 KB	Output is correct
16	Correct	10 ms	11864 KB	Output is correct
17	Correct	10 ms	12636 KB	Output is correct
18	Correct	11 ms	12636 KB	Output is correct
19	Correct	10 ms	12544 KB	Output is correct
20	Correct	10 ms	12712 KB	Output is correct
21	Correct	11 ms	12636 KB	Output is correct
22	Correct	11 ms	12636 KB	Output is correct
23	Correct	10 ms	12700 KB	Output is correct
24	Correct	11 ms	12636 KB	Output is correct
25	Correct	11 ms	12636 KB	Output is correct
26	Correct	11 ms	12636 KB	Output is correct
27	Correct	11 ms	12704 KB	Output is correct
28	Correct	11 ms	12632 KB	Output is correct
29	Correct	11 ms	12636 KB	Output is correct
30	Correct	10 ms	12124 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	1 ms	604 KB	Output is correct
2	Correct	0 ms	616 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	2 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	2 ms	2392 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1628 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	604 KB	Output is correct
13	Correct	2 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	1992 KB	Output is correct
18	Correct	1 ms	2140 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	2136 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	2 ms	2136 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	1880 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	616 KB	Output is correct
3	Correct	0 ms	860 KB	Output is correct
4	Correct	2 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	2 ms	2392 KB	Output is correct
8	Correct	1 ms	2140 KB	Output is correct
9	Correct	1 ms	1628 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	604 KB	Output is correct
13	Correct	2 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	1992 KB	Output is correct
18	Correct	1 ms	2140 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	2136 KB	Output is correct
26	Correct	1 ms	2140 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	2 ms	2136 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	1880 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #1087845

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