Submission #1065309

#TimeUsernameProblemLanguageResultExecution timeMemory
1065309Dan4LifeToy (CEOI24_toy)C++17
35 / 100
9 ms14172 KiB
#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]=-n*m*n*m; 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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...