Submission #535554

#TimeUsernameProblemLanguageResultExecution timeMemory
535554MOUF_MAHMALATSelotejp (COCI20_selotejp)C++14
110 / 110
166 ms41180 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() #define F first #define S second using namespace std; typedef int ll; ll n,m,dp[10][1000][1<<10],o; bool b[1000][10]; ll best(ll j,ll d,ll mask) { if(j==m) { j=0; d++; } if(d==n) return 0; ll &r=dp[j][d][mask]; if(r!=-1) return r; if(!b[d][j]) return r=best(j+1,d,mask&(o^(1<<j))); if(j&&((mask&(1<<(j-1)))==0)&&b[d][j-1]) r=best(j+1,d,mask&(o^(1<<j))); else r=best(j+1,d,mask&(o^(1<<j)))+1; if((mask&(1<<j))!=0) r=min(r,best(j+1,d,mask)); else r=min(r,best(j+1,d,mask|(1<<j))+1); return r; } int main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(ll i=0; i<n; i++) for(ll j=0; j<m; j++) { char c; cin>>c; if(c=='#') b[i][j]=1; } o=(1<<m)-1; memset(dp,-1,sizeof dp); cout<<best(0,0,0); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...