#pragma GCC optimize("Ofast") #include using namespace std; #ifdef __LOCAL #include #else #define debug(...) void(0) #endif #define REP(i,n) for(int i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() template istream& operator>>(istream&is,vector&v){ for(T&p:v)is>>p; return is; } template ostream& operator<<(ostream&os,const vector&v){ if(&os==&cerr)os<<"["; for(int i=0;i=0 and y=0 and x void fin(T a){ cout< bool chmax(T &a,T b){ return (a>n>>v>>ox>>oy; ox--;oy--; vector l(n,vector(n)); cin>>l; vector d(n,vector(n,-1)); priority_queue> que; d[0][0]=v; que.emplace(v,0,0); while(que.size()){ auto [va,y,x]=que.top();que.pop(); if(d[y][x]>va)continue; REP(dd,4){ int Y=y+dy[dd],X=x+dx[dd]; if(!inyx(Y,X,n,n))continue; if(chmax(d[Y][X],va-l[Y][X])) que.emplace(d[Y][X],Y,X); } } if(d[n-1][n-1]>0)fin("YES"); if(ox<0||d[oy][ox]<=0)fin("NO"); v=d[oy][ox]*2; REP(i,n)REP(j,n)d[i][j]=-1; d[oy][ox]=v; que.emplace(v,oy,ox); while(que.size()){ auto [va,y,x]=que.top();que.pop(); if(d[y][x]>va)continue; REP(dd,4){ int Y=y+dy[dd],X=x+dx[dd]; if(!inyx(Y,X,n,n))continue; if(chmax(d[Y][X],va-l[Y][X])) que.emplace(d[Y][X],Y,X); } } if(d[n-1][n-1]>0)fin("YES"); fin("NO"); }