Submission #1045689

#TimeUsernameProblemLanguageResultExecution timeMemory
1045689gagik_2007Toy (CEOI24_toy)C++17
35 / 100
762 ms765016 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=93; ll n,m,k; int h, v; bool dp[N][N][N][N]; bool vis[N][N][N][N]; bool d[N][N]; int pf[N][N]; int colpf[N][N]; int tgi,tgj; int getPf(int i, int j1, int j2){ if(j1==0)return pf[i][j2]; return pf[i][j2]-pf[i][j1-1]; } int getColPf(int j, int i1, int i2){ if(i1==0)return colpf[j][i2]; return colpf[j][i2]-colpf[j][i1-1]; } void recurs(int i, int j, int lh, int lv){ if(vis[i][j][lh][lv])return; vis[i][j][lh][lv]=true; if(!dp[i][j][lh][lv])return; // cout<<i<<" "<<j<<" "<<lh<<" "<<lv<<endl; int hi=i,hj=j-lh; int vi=i-lv,vj=j; // H movement //up if(i>0&&lv>0&&getPf(hi-1,hj,hj+h-1)==0){ dp[i-1][j][lh][lv-1]=true; recurs(i-1,j,lh,lv-1); } //down if(i<n-1&&lv<v-1&&getPf(hi+1,hj,hj+h-1)==0){ dp[i+1][j][lh][lv+1]=true; recurs(i+1,j,lh,lv+1); } //left if(hj>0&&lh<h-1&&!d[i][hj-1]){ dp[i][j][lh+1][lv]=true; recurs(i,j,lh+1,lv); } //right if(hj+h<m&&lh>0&&!d[i][hj+h]){ dp[i][j][lh-1][lv]=true; recurs(i,j,lh-1,lv); } // V movement //up if(vi>0&&lv<v-1&&!d[vi-1][j]){ dp[i][j][lh][lv+1]=true; recurs(i,j,lh,lv+1); } //down // cout<<vi+v<<" < "<<n<<" && "<<lv<<" > 0 && !"<<d[vi+v][j]<<endl; if(vi+v<n&&lv>0&&!d[vi+v][j]){ dp[i][j][lh][lv-1]=true; recurs(i,j,lh,lv-1); } //left if(j>0&&lh>0&&getColPf(j-1,vi,vi+v-1)==0){ dp[i][j-1][lh-1][lv]=true; recurs(i,j-1,lh-1,lv); } //right if(j<m-1&&lh<h-1&&getColPf(j+1,vi,vi+v-1)==0){ dp[i][j+1][lh+1][lv]=true; recurs(i,j+1,lh+1,lv); } } void calculatePfs(){ for(int i=0;i<n;i++){ pf[i][0]=d[i][0]; for(int j=1;j<m;j++){ pf[i][j]=pf[i][j-1]+d[i][j]; } } for(int j=0;j<m;j++){ colpf[j][0]=d[0][j]; for(int i=1;i<n;i++){ colpf[j][i]=colpf[j][i-1]+d[i][j]; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("Dinput.txt","r",stdin); // freopen("Doutput.txt","w",stdout); cin>>m>>n; cin>>h>>v; int i1,i2,j1,j2; cin>>j1>>i1>>j2>>i2; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ char c; cin>>c; // cout<<c; if(c=='X'){ d[i][j]=true; } if(c=='*'){ tgi=i; tgj=j; // cout<<i<<" "<<j<<endl; } } // cout<<endl; } calculatePfs(); int ii=i1; int jj=j2; int lh=jj-j1; int lv=ii-i2; dp[ii][jj][lh][lv]=true; recurs(ii,jj,lh,lv); for(lh=0;lh<h;lh++){ for(lv=0;lv<v;lv++){ if(dp[tgi][tgj][lh][lv]){ // cout<<tgi<<" "<<tgj<<endl; // cout<<lh<<" "<<lv<<endl; cout<<"YES"<<endl; return 0; } } } cout<<"NO"<<endl; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void recurs(int, int, int, int)':
Main.cpp:42:17: warning: unused variable 'vj' [-Wunused-variable]
   42 |     int vi=i-lv,vj=j;
      |                 ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...