oj.uz

Submission #1087830

# Submission time Handle Problem Language Result Execution time Memory
1087830 2024-09-13T09:49:36 Z mychecksedad Toy (CEOI24_toy) C++17
0 / 100
 9 ms 6756 KB 
#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];
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] = 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 - 1; i1 >= i - l + 1; --i1)
					if(get(i1, i, j, j) == 0 && V[i1][j]) V[i][j] = 1;
			for(int i1 = j - 1; i1 >= j - k + 1; --i1)
					if(get(i, i, i1, j) == 0 && H[i][i1]) H[i][j] = 1;
		}
	}
	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 && V[nx][ny] == 1 && H[nx][ny] == 1 && !vis[nx][ny]){
				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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1348 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1280 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 2 ms 1116 KB Output is correct
29 Correct 1 ms 1368 KB Output is correct
30 Correct 1 ms 1112 KB Output is correct
31 Correct 1 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1116 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Incorrect 1 ms 1116 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1348 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1280 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 2 ms 1116 KB Output is correct
29 Correct 1 ms 1368 KB Output is correct
30 Correct 1 ms 1112 KB Output is correct
31 Correct 1 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1116 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Incorrect 1 ms 1116 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 8 ms 6756 KB Output is correct
5 Correct 8 ms 6748 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 8 ms 6748 KB Output is correct
8 Correct 9 ms 6744 KB Output is correct
9 Correct 2 ms 2704 KB Output is correct
10 Correct 5 ms 6528 KB Output is correct
11 Correct 4 ms 6580 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 4 ms 6748 KB Output is correct
14 Correct 5 ms 6748 KB Output is correct
15 Correct 7 ms 6420 KB Output is correct
16 Correct 7 ms 6236 KB Output is correct
17 Correct 7 ms 6712 KB Output is correct
18 Correct 7 ms 6748 KB Output is correct
19 Correct 7 ms 6620 KB Output is correct
20 Correct 7 ms 6748 KB Output is correct
21 Correct 7 ms 6656 KB Output is correct
22 Correct 8 ms 6744 KB Output is correct
23 Correct 7 ms 6748 KB Output is correct
24 Correct 7 ms 6748 KB Output is correct
25 Correct 7 ms 6492 KB Output is correct
26 Correct 8 ms 6748 KB Output is correct
27 Correct 7 ms 6492 KB Output is correct
28 Correct 8 ms 6744 KB Output is correct
29 Correct 7 ms 6752 KB Output is correct
30 Correct 7 ms 6492 KB Output is correct
31 Correct 7 ms 6488 KB Output is correct
32 Correct 7 ms 6736 KB Output is correct
33 Correct 7 ms 6236 KB Output is correct
34 Correct 6 ms 6232 KB Output is correct
35 Correct 7 ms 6236 KB Output is correct
36 Correct 5 ms 6524 KB Output is correct
37 Incorrect 7 ms 6372 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1348 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1280 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 2 ms 1116 KB Output is correct
29 Correct 1 ms 1368 KB Output is correct
30 Correct 1 ms 1112 KB Output is correct
31 Correct 1 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1116 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Incorrect 1 ms 1116 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1348 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1280 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 2 ms 1116 KB Output is correct
29 Correct 1 ms 1368 KB Output is correct
30 Correct 1 ms 1112 KB Output is correct
31 Correct 1 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1116 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Incorrect 1 ms 1116 KB Output isn't correct
38 Halted 0 ms 0 KB -