Submission #1140579

#TimeUsernameProblemLanguageResultExecution timeMemory
1140579RafiullahToy (CEOI24_toy)C++20
0 / 100
1599 ms783224 KiB
#include<bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
#define int long long
const int N = 91;
const int mod = 1e9 + 7;
const int mod1 = 998244353;
const int LG = 20;
// #define s(i) (*s.find_by_order(i)) // Warning : Read this line.

int power(int b,int e){
    if(e<=0)return 1;
    int o = power(b,e>>1);
    o *= o, o %= mod1;
    if(e % 2)o *= b, o %= mod1;
    return o;
}
vector<string> grid;int k,l, n, m;
int h[2],v[2], lef[N][N], upp[N][N];
map<vector<int>,bool> dp;
int f(int x, int y, int up, int right ){
    if(y - up < 0 or y - up + l - 1>=n or x + right >= m or x + right - k + 1 < 0 or up >= l or right >= k or up < 0 or right < 0 or x < 0 or x >= m or y < 0 or y >= n)return 0;
    if(upp[x][y-up+l-1]<l or lef[x+right][y]<k)return dp[{x,y,up,right}]=0;
    if(dp[{x,y,up,right}]==2)return 0;
    if(dp[{x,y,up,right}] != -1)return dp[{x,y,up,right}];
    bool ft = false;
    dp[{x,y,up,right}] = 2;
    //vertical movements
    ft |= f(x,y,up-1,right);
    ft |= f(x,y,up+1,right);
    ft |= f(x,y,up, right-1);
    ft |= f(x,y, up,right+1);
    ft |= f(x+1,y,up,right-1);
    ft |= f(x-1, y,up,right+1);
    ft |= f(x, y-1,up-1,right);
    ft |= f(x,y+1,up+1,right);
    dp[{x,y,up,right}] = ft;
    return dp[{x,y,up,right}];
}
void solve(){//k horizontal, l vertical
    cin >> m >> n >> k >> l;
    cin >> h[0] >> h[1] >> v[0] >> v[1];
    for(int i = 0 ; i < n ; i ++){
        string t;cin >> t;
        grid.push_back(t);
    }
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < m ; j ++)
            for(int e = 0 ; e < l ; e ++)
                for(int t = 0 ; t < k ; t ++)
                    dp[{j,i,e,t}] = -1;
    int px = -1,py=-1;
    int ix = v[0], iy = h[1];
    int up = iy - v[1];
    int right = k - (ix - h[0] + 1);
    // cout << ix << ' ' << iy << ' ' << up << ' ' << right<< '\n';
    dp[{ix,iy,up,right}] = 1;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < m ; j ++){
            if(grid[i][j] == '*'){
                px = j, py = i;
            }
            lef[j][i] = upp[j][i] = 1;
            if(grid[i][j] == 'X')lef[j][i]=0,upp[j][i]= 0;
            else{
                if(j>0)lef[j][i] += lef[j - 1][i];
                if(i>0)upp[j][i] += upp[j][i - 1];
            }
        }
    // cout << px << ' ' << py << '\n';
    // f(px,py,0,0);
    int ans = 0;
    for(int i = 0 ; i < l ; i ++)
        for(int j = 0 ; j < k ; j ++)
            ans |= f(px,py,i,j);
    if(ans)cout << "YES" << '\n';
    else cout << "NO" << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}
#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...