Submission #1066377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066377		AlgorithmWarrior	Toy (CEOI24_toy)	C++14	100 / 100	449 ms	372576 KiB

Main

#include <bits/stdc++.h>
#define MAX 3005

using namespace std;

bool mat[MAX][MAX];
int nrobsv[MAX][MAX],nrobso[MAX][MAX];
int nrdreptv[MAX][MAX],nrdrepto[MAX][MAX];
bool sol[MAX][MAX];
int m,n,c,l;

void myfill(int i,int j)
{
    sol[i][j]=1;
    if(nrdrepto[i-1][j+c-1] && !sol[i-1][j])
        myfill(i-1,j);
    if(nrdrepto[i][j+c-1] && !sol[i+1][j])
        myfill(i+1,j);
    if(nrdreptv[i+l-1][j] && !sol[i][j+1])
        myfill(i,j+1);
    if(nrdreptv[i+l-1][j-1] && !sol[i][j-1])
        myfill(i,j-1);
}

int main()
{
    memset(mat,1,sizeof(mat));
    cin>>m>>n>>c>>l;
    int xh,yh,xv,yv;
    cin>>xh>>yh>>xv>>yv;
    int i,j;
    int starl,starc;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            char ch;
            cin>>ch;
            mat[i][j]=(ch=='X') ? 1 : 0;
            if(ch=='*')
            {
                starl=i;
                starc=j;
            }
        }
    for(j=1;j<m+c;++j)
        nrobsv[0][j]=2*l;
    for(i=1;i<n+l;++i)
        nrobso[i][0]=2*c;
    for(i=1;i<n+l;++i)
        for(j=1;j<m+c;++j)
        {
            nrobsv[i][j]=nrobsv[i-1][j]-(i-l<=0 || mat[i-l][j])-(i-l<=0 || mat[i-l][j+1])+mat[i][j]+mat[i][j+1];
            nrobso[i][j]=nrobso[i][j-1]-(j-c<=0 || mat[i][j-c])-(j-c<=0 || mat[i+1][j-c])+mat[i][j]+mat[i+1][j];
            nrdreptv[i][j]=nrdreptv[i-1][j]-(i-l>0 && !nrobsv[i-l][j])+(!nrobsv[i][j]);
            nrdrepto[i][j]=nrdrepto[i][j-1]-(j-c>0 && !nrobso[i][j-c])+(!nrobso[i][j]);
        }
    myfill(yh+1,xv+1);
    cout<<((sol[starl][starc]) ? "YES" : "NO");
    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