Submission #1140566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140566		Rafiullah	Toy (CEOI24_toy)	C++20	23 / 100	1063 ms	1114112 KiB

Main

#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 = 301;
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];
vector<vector<vector<vector<int>>>> 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;
    // cout << dp[x][y][up][right] << ' ' << x << ' ' << y << ' ' << up << ' ' << right << '\n';
    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);
    }
    vector<vector<vector<vector<int>>>> p(m+1,vector<vector<vector<int>>>(n+1,vector<vector<int>>(l+1,vector<int>(k+1))));
    dp = p;
    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();
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 0 / 21
• Subtask 3: 9 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27