Submission #1239913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239913		Petrix	Toy (CEOI24_toy)	C++20	100 / 100	166 ms	110664 KiB

Main

#include <iostream>
using namespace std;

string v[1501];
bool viz[1501][1501];
int st[1501][1501],dr[1501][1501],sus[1501][1501],jos[1501][1501];
int n,m,lat,ina;
bool dfs(int l,int c){

    int stg=0;
	if(viz[l][c]) return 0;
	viz[l][c]=1;if(v[l][c]=='*') return 1;
	///printf("%d %d %d %d\n",l,c,min(st[l-1][c],st[l][c])+min(dr[l-1][c],dr[l][c])),lat;
	if(l>1 && min(st[l-1][c],st[l][c])+min(dr[l-1][c],dr[l][c])>lat && dfs(l-1,c)) stg=1;
	if(l<=n-1 && min(st[l+1][c],st[l][c])+min(dr[l+1][c],dr[l][c])>lat && dfs(l+1,c)) stg=1;
	if(c>1 && min(sus[l][c-1],sus[l][c])+min(jos[l][c-1],jos[l][c])>ina && dfs(l,c-1)) stg=1;
	if(c<=m-1 && min(sus[l][c+1],sus[l][c])+min(jos[l][c+1],jos[l][c])>ina && dfs(l,c+1)) stg=1;
	return stg;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int l1,c1,l2,c2,i,stg,j;
    cin>>n>>m>>lat>>ina>>l1>>c1>>l2>>c2;
    l1++;c1++;l2++;c2++;
    swap(n,m);swap(l1,c1);swap(l2,c2);
    for(i=1;i<=n;i++){
        cin>>v[i];v[i]=" "+v[i];
        for(j=1;j<=m;j++){
            st[i][j]=dr[i][j]=sus[i][j]=jos[i][j]=-1e9;
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(v[i][j]=='X') continue;
            st[i][j]=sus[i][j]=1;
            if(i>1) sus[i][j]+=max(0,sus[i-1][j]);
            if(j>1) st[i][j]+=max(0,st[i][j-1]);
        }
    }
    for(i=n;i;i--){
        for(j=m;j;j--){
            if(v[i][j]=='X') continue;
            dr[i][j]=jos[i][j]=1;
            if(i!=n) jos[i][j]+=max(0,jos[i+1][j]);
            if(j!=m) dr[i][j]+=max(0,dr[i][j+1]);
        }
    }
    ///cout<<min(st[1][4],st[2][4])+min(dr[1][4],dr[2][4])<<"|\n";
    stg=dfs(l1,c2);
    if(stg) cout<<"YES";
    else cout<<"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