Submission #1318284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318284		HoriaHaivas	Toy (CEOI24_toy)	C++20	100 / 100	452 ms	339628 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

bool wall[1505][1505];
bool visited[1505][1505];
int dp[1505][1505];
int nextl[1505][1505];
int nextr[1505][1505];
int nextu[1505][1505];
int nextd[1505][1505];
int n,m,k,l;

bool inmat(int r, int c)
{
    return ((r>0 && r<=n) && (c>0 && c<=m));
}

void dfs(int r, int c)
{
    if (visited[r][c])
        return;
    visited[r][c]=1;
    ///mergem in jos
    int st,up;
    if (inmat(r+1,c) && !wall[r+1][c] && (min(nextr[r][c],nextr[r+1][c])-max(nextl[r][c],nextl[r+1][c]))>k)
    {
        dp[r+1][c]=1;
        dfs(r+1,c);
    }
    ///mergem in sus
    if (inmat(r-1,c) && !wall[r-1][c] && (min(nextr[r][c],nextr[r-1][c])-max(nextl[r][c],nextl[r-1][c]))>k)
    {
        dp[r-1][c]=1;
        dfs(r-1,c);
    }
    ///mergem la stanga
    if (inmat(r,c-1) && !wall[r][c-1] && (min(nextd[r][c],nextd[r][c-1])-max(nextu[r][c],nextu[r][c-1]))>l)
    {
        dp[r][c-1]=1;
        dfs(r,c-1);
    }
    ///mergem la dreapta
    if (inmat(r,c+1) && !wall[r][c+1] && (min(nextd[r][c],nextd[r][c+1])-max(nextu[r][c],nextu[r][c+1]))>l)
    {
        dp[r][c+1]=1;
        dfs(r,c+1);
    }
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i,j,xh,yh,xv,yv,r,c,last,fr,fc;
    char ch;
    cin >> m >> n >> k >> l;
    cin >> yh >> xh >> yv >> xv;
    yh++;
    xh++;
    yv++;
    xv++;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            cin >> ch;
            if (ch=='X')
                wall[i][j]=1;
            else
                wall[i][j]=0;
            if (ch=='*')
            {
                fr=i;
                fc=j;
            }
        }
    }
    for (i=1; i<=n; i++)
    {
        last=0;
        for (j=1; j<=m; j++)
        {
            if (wall[i][j])
                last=j;
            nextl[i][j]=last;
        }
        last=m+1;
        for (j=m; j>=1; j--)
        {
            if (wall[i][j])
                last=j;
            nextr[i][j]=last;
        }
    }
    for (j=1; j<=m; j++)
    {
        last=0;
        for (i=1; i<=n; i++)
        {
            if (wall[i][j])
                last=i;
            nextu[i][j]=last;
        }
        last=n+1;
        for (i=n; i>=1; i--)
        {
            if (wall[i][j])
                last=i;
            nextd[i][j]=last;
        }
    }
    r=xh;
    c=yv;
    dp[r][c]=1;
    dfs(r,c);
    if (dp[fr][fc])
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

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