#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 time |
Memory |
Grader output |
1 |
Correct |
17 ms |
40404 KB |
Output is correct |
2 |
Correct |
21 ms |
41140 KB |
Output is correct |
3 |
Correct |
20 ms |
40932 KB |
Output is correct |
4 |
Correct |
22 ms |
41100 KB |
Output is correct |
5 |
Correct |
22 ms |
41172 KB |
Output is correct |
6 |
Correct |
23 ms |
41100 KB |
Output is correct |
7 |
Correct |
21 ms |
41172 KB |
Output is correct |
8 |
Correct |
19 ms |
41068 KB |
Output is correct |
9 |
Correct |
20 ms |
41136 KB |
Output is correct |
10 |
Correct |
40 ms |
41112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
40400 KB |
Output is correct |
2 |
Correct |
18 ms |
40396 KB |
Output is correct |
3 |
Correct |
17 ms |
40376 KB |
Output is correct |
4 |
Correct |
18 ms |
40272 KB |
Output is correct |
5 |
Correct |
17 ms |
40404 KB |
Output is correct |
6 |
Correct |
17 ms |
40324 KB |
Output is correct |
7 |
Correct |
17 ms |
40404 KB |
Output is correct |
8 |
Correct |
17 ms |
40308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
40404 KB |
Output is correct |
2 |
Correct |
21 ms |
41140 KB |
Output is correct |
3 |
Correct |
20 ms |
40932 KB |
Output is correct |
4 |
Correct |
22 ms |
41100 KB |
Output is correct |
5 |
Correct |
22 ms |
41172 KB |
Output is correct |
6 |
Correct |
23 ms |
41100 KB |
Output is correct |
7 |
Correct |
21 ms |
41172 KB |
Output is correct |
8 |
Correct |
19 ms |
41068 KB |
Output is correct |
9 |
Correct |
20 ms |
41136 KB |
Output is correct |
10 |
Correct |
40 ms |
41112 KB |
Output is correct |
11 |
Correct |
18 ms |
40400 KB |
Output is correct |
12 |
Correct |
18 ms |
40396 KB |
Output is correct |
13 |
Correct |
17 ms |
40376 KB |
Output is correct |
14 |
Correct |
18 ms |
40272 KB |
Output is correct |
15 |
Correct |
17 ms |
40404 KB |
Output is correct |
16 |
Correct |
17 ms |
40324 KB |
Output is correct |
17 |
Correct |
17 ms |
40404 KB |
Output is correct |
18 |
Correct |
17 ms |
40308 KB |
Output is correct |
19 |
Correct |
18 ms |
40768 KB |
Output is correct |
20 |
Correct |
25 ms |
40956 KB |
Output is correct |
21 |
Correct |
25 ms |
41052 KB |
Output is correct |
22 |
Correct |
19 ms |
41076 KB |
Output is correct |
23 |
Correct |
21 ms |
41140 KB |
Output is correct |
24 |
Correct |
20 ms |
41172 KB |
Output is correct |
25 |
Correct |
29 ms |
41176 KB |
Output is correct |
26 |
Correct |
53 ms |
41044 KB |
Output is correct |
27 |
Correct |
97 ms |
41180 KB |
Output is correct |
28 |
Correct |
166 ms |
41172 KB |
Output is correct |