#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7,Inf=10000;
int t,n,a[1050][15],dp[1005][1050],f[N],cost[N],r;
main(){
cin>>n>>r;
for(int i=1;i<=n;i++){
for(int j=0;j<r;j++) {
char c;
cin>>c;
if(c == '#') a[i][j] = 1;
}
}
for(int j=0;j<=n;j++)
for(int i=0;i<(1<<r);i++){
dp[j][i] = Inf;
}
dp[0][0] = 0;
int ans = Inf;
for(int i=1;i<=n;i++) {
int mask = 0;
for(int j=0;j<r;j++) {
mask +=(1<<j)*a[i][j];
}
f[0] = 1;
for(int m = mask;;m=mask&(m-1)) {
f[m] = 1; cost[m^mask] = 0;
for(int k=0;k<m;k++){
int j = k;
if((1<<k)&m) {
cost[m^mask]++;
while((1<<(j+1))&m) j++;
k = j;
}
}
if(!m) break;
}
for(int j=0;j<(1<<r);j++) {
if(!f[j]) continue;
for(int m=j;;m=(m-1)&j) {
dp[i][j] = min(dp[i][j],dp[i-1][m] + cost[j] + __builtin_popcount(j^m));
if(i == n) ans = min(ans,dp[i][j]);
if(!m) break;
}
f[j] = 0;
}
for(int j=0;j<(1<<r);j++) {
for(int m = j;;m=j&(m-1)) {
dp[i][m] = min(dp[i][j],dp[i][m]);
if(!m) break;
}
}
}
cout<<ans;
}
Compilation message
Main.cpp:8:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
8 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
