This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fore(i, a, b) for (ll i = (a), _b = (b); i < (_b); i++)
#define fort(i, a, b) for (ll i = (a), _b = (b); i <= (_b); i++)
#define ford(i, a, b) for (ll i = (a), _b = (b); i >= (_b); i--)
#define fi first
#define se second
#define sz(x) ((ll)(x).size())
#define getbit(x, i) ((x) & (1LL << (i)))
#define on(x, i) ((x) | (1LL << (i)))
#define off(x, i) ((x) ^ (1LL << (i)))
#define lowbit(x) ((x) & (-(x)))
#define pb push_back
#define pf push_front
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
bool mini(ll &a, const ll b) {
if (a > b) {
a = b;
return true;
}
return false;
}
bool maxi(ll &a, const ll b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const ll maxM = 1005;
const ll inf = 1e18;
const ll maxN = 10;
ll m, n, full, choco[maxM];
ll cntbit[1LL << maxN], row[1LL << maxN], dp[maxM][1LL << maxN];
vi submsk[1LL << maxN];
bool vis[maxM][1LL << maxN];
char c[maxM][maxN];
ll CountBit(ll x) {
ll res = 0;
for (; x > 0; x -= lowbit(x))
res++;
return res;
}
ll costRow(ll msk) {
ll res = 0;
vi row;
row.pb(0);
fore(i, 0 , n)
row.pb((bool)getbit(msk, i));
fore(i, 1, sz(row))
if (row[i] == 1 && !row[i - 1])
res++;
return res;
}
ll DP(ll i, ll prv) {
if (i > m)
return 0;
if (!vis[i][prv]) {
vis[i][prv] = true;
dp[i][prv] = inf;
// fort(cols, 0, full)
// if ((choco[i] & cols) == cols) {
// mini(dp[i][prv], cntbit[cols] - cntbit[cols & prv] + row[choco[i] ^ cols] + DP(i + 1, cols & choco[i + 1]));
// }
ll cols;
for (vi::iterator j = submsk[choco[i]].begin(); j != submsk[choco[i]].end(); j++) {
cols = *j;
mini(dp[i][prv], cntbit[cols] - cntbit[cols & prv] + row[choco[i] ^ cols] + DP(i + 1, cols));
}
}
return dp[i][prv];
}
void input() {
cin >> m >> n;
fort(i, 1, m) {
cin >> c[i];
fore(j, 0, n)
if (c[i][j] == '#')
choco[i] |= (1LL << j);
}
}
void solve() {
//preprocess
full = (1LL << n) - 1;
fort(i, 0, full) {
row[i] = costRow(i);
cntbit[i] = CountBit(i);
fort(j, 0, full)
if ((i & j) == j)
submsk[i].pb(j);
}
//main solve
cout << DP(1, 0) << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |