#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define BIT(mask,x) ((mask)>>(x)&(1))
#define MASK(x) ((ll)(1)<<(x))
#define all(datastructure) datastructure.begin(),datastructure.end()
void compress(vector<int>&x){
x.resize(unique(all(x))-x.begin());
}
template <class T1 , class T2>
bool minU(T1 &a, T2 b){
if (a>b) return a = b , true;
return false;
}
template <class T1 , class T2>
bool maxU(T1 &a, T2 b){
if (a<b) return a = b,true;
return false;
}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int Rand(int l , int r){
return uniform_int_distribution<int> (l,r)(rng);
}
const int maxn = 1000;
const int maxm = 10;
int numrow,numcol;
bool c[maxn+2][maxm+2];
int a[maxn+2][MASK(maxm)];
int dp[maxn+2][MASK(maxm)];
int f[maxn+2][MASK(maxm)];
int un[maxn+2][MASK(maxm)];
bool can[MASK(maxm)];
bool ok(int id , int mask){
for (int i = 0; i < numcol; ++i){
if (BIT(mask,i) && c[id][i]==false) return false;
}
return true;
}
int calc(int id , int mask){
int mask2 = mask;
int ans = 0 , cnt = 0 , ngang = 0;
for (int i = 0; i < numcol; ++i){
if (BIT(mask,i)){
ans += ngang;
ngang = 0;
}
else {
if (c[id][i]==false){
ans += ngang;
ngang = 0;
}
else
if (i==0||BIT(mask,i-1)||c[id][i-1]==false) ngang = 1;
}
};
ans += ngang;
int res = min(un[id-1][mask],f[id-1][mask]);
return res + ans;
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> numrow >> numcol;
for (int i = 1; i <= numrow; ++i){
for (int j = 0; j < numcol; ++j){
char x; cin >> x;
if (x=='#') c[i][j] = true; else c[i][j] = false;
}
}
memset(dp,0x3f,sizeof dp);
memset(f,0x3f,sizeof f);
memset(un,0x3f,sizeof un);
for (int i = 0; i < numcol; ++i) c[0][i] = false;
for (int mask = 0; mask < MASK(numcol); ++mask) un[0][mask] = __builtin_popcount(mask);
for (int i = 1; i <= numrow;++i){
for (int mask = 0; mask < MASK(numcol); ++mask){
can[mask] = ok(i,mask);
if (can[mask])
dp[i][mask] = calc(i,mask);
}
for (int mask = 0; mask < MASK(numcol); ++mask){
un[i][mask] = dp[i][mask];
}
for (int j = 0; j < numcol; ++j){
for (int mask = 0; mask < MASK(numcol); ++mask){
if (BIT(mask,j) && can[mask])
un[i][mask] = min(un[i][mask] , un[i][mask^MASK(j)] + 1);
}
}
for (int mask = 0; mask < MASK(numcol); ++mask){
f[i][mask] = min(un[i][mask] , dp[i][mask]);
}
for (int j = 0; j < numcol; ++j){
for (int mask = MASK(numcol)-1; mask >= 0; --mask){
if (!BIT(mask,j) && can[mask])
f[i][mask] = min(f[i][mask] , f[i][mask|MASK(j)] - 1);
}
}
}
int ans = numrow*numcol;
for (int mask = 0; mask < MASK(numcol); ++mask)
{
ans = min(dp[numrow][mask],ans);
}
cout << ans;
}
Compilation message
Main.cpp: In function 'long long int calc(long long int, long long int)':
Main.cpp:43:6: warning: unused variable 'mask2' [-Wunused-variable]
43 | int mask2 = mask;
| ^~~~~
Main.cpp:44:16: warning: unused variable 'cnt' [-Wunused-variable]
44 | int ans = 0 , cnt = 0 , ngang = 0;
| ^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:70:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:71:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
25168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
25168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
25168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
