Submission #1065317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065317		Dan4Life	Toy (CEOI24_toy)	C++17	100 / 100	303 ms	357568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using vi = vector<int>;
using ll = long long;
const int mxN = (int)1510;

string a[mxN];
int n, m, H, V;
int hr, hc, vr, vc;
bitset<mxN> vis[mxN];
int l[mxN][mxN], r[mxN][mxN], u[mxN][mxN], d[mxN][mxN];

bool dfs(int i, int j){
	if(vis[i][j]) return 0;
	vis[i][j]=1; if(a[i][j]=='*') return 1;
	if(i>0   and min(l[i-1][j],l[i][j])+min(r[i-1][j],r[i][j])>H and dfs(i-1,j)) return 1;
	if(i<n-1 and min(l[i+1][j],l[i][j])+min(r[i+1][j],r[i][j])>H and dfs(i+1,j)) return 1;
	if(j>0   and min(u[i][j-1],u[i][j])+min(d[i][j-1],d[i][j])>V and dfs(i,j-1)) return 1;
	if(j<m-1 and min(u[i][j+1],u[i][j])+min(d[i][j+1],d[i][j])>V and dfs(i,j+1)) return 1;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> H >> V >> hr >> hc >> vr >> vc;
	swap(n,m), swap(hr,hc), swap(vr,vc);
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			l[i][j]=u[i][j]=r[i][j]=d[i][j]=-(int)1e9;
			if(a[i][j]=='X') continue;
			l[i][j]=u[i][j]=1;
			if(i) u[i][j]+=max(0,u[i-1][j]);
			if(j) l[i][j]+=max(0,l[i][j-1]);
		}
	}
	for(int i = n-1; i >= 0; i--){
		for(int j = m-1; j >= 0; j--){
			if(a[i][j]=='X') continue;
			r[i][j]=d[i][j]=1;
			if(i!=n-1) d[i][j]+=max(0,d[i+1][j]);
			if(j!=m-1) r[i][j]+=max(0,r[i][j+1]);
		}
	}
	cout << (dfs(hr,vc)?"YES":"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