Submission #1197874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197874		user736482	Toy (CEOI24_toy)	C++20	100 / 100	179 ms	78064 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll w,h,k,l,a,b,c;
queue<pair<ll,ll>>q;
bool poss[1507][1507],czy[1507][1507],czy2[1507][1507];
ll lw[1507][1507],pw[1507][1507],d[1507][1507],g[1507][1507];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>w>>h>>k>>l>>a>>b>>c>>a;
    a=c;
    q.push({a,b});
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
            char ch;
            cin>>ch;
            czy2[j][i]=(ch=='*');
            czy[j][i]=!(ch=='X');
        }
    }
    for(ll i=0;i<h;i++)lw[0][i]=czy[0][i];
    for(ll j=1;j<w;j++)for(ll i=0;i<h;i++)lw[j][i]=(lw[j-1][i]+1)*czy[j][i];
    for(ll i=0;i<h;i++)pw[w-1][i]=czy[w-1][i];
    for(ll j=w-2;j>=0;j--)for(ll i=0;i<h;i++)pw[j][i]=(pw[j+1][i]+1)*czy[j][i];
    for(ll i=0;i<w;i++)g[i][0]=czy[i][0];
    for(ll j=1;j<h;j++)for(ll i=0;i<w;i++)g[i][j]=(g[i][j-1]+1)*czy[i][j];
    for(ll i=0;i<w;i++)d[i][h-1]=czy[i][h-1];
    for(ll j=h-2;j>=0;j--)for(ll i=0;i<w;i++)d[i][j]=(d[i][j+1]+1)*czy[i][j];
    while(q.size()){
        auto pom=q.front();
        q.pop();
        if(czy2[pom.ff][pom.ss]){
            cout<<"YES";return 0;
        }
        if(poss[pom.ff][pom.ss])continue;
        poss[pom.ff][pom.ss]=1;
        a=pom.ff;
        b=pom.ss;
        if(a && min(d[a][b],d[a-1][b])+min(g[a][b],g[a-1][b])>l)q.push({a-1,b});
        if(a<w-1 && min(d[a][b],d[a+1][b])+min(g[a][b],g[a+1][b])>l)q.push({a+1,b});
        if(b && min(lw[a][b],lw[a][b-1])+min(pw[a][b],pw[a][b-1])>k)q.push({a,b-1});
        if(b<h-1 && min(lw[a][b],lw[a][b+1])+min(pw[a][b],pw[a][b+1])>k)q.push({a,b+1});
    }
    cout<<"NO";
}

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